Python with pruned backtracking, easily understand

  • 0

    The index from the candidates is used as the stack to avoid duplicates.

    def combinationSum2(self, candidates, target):
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        result = []
        def dfs(remain, stack):
            if not remain:
                result.append([candidates[i] for i in stack])
            if not stack: c = 0
            else: c = stack[-1]+1
            for i in xrange(c, len(candidates)):
                item = candidates[i]
                if i > c and item == candidates[i-1]: continue
                if item > remain: break
                dfs(remain-item, stack + [i])
        dfs(target, [])
        return result

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.