Python backtracking

  • 0
    class Solution(object):
        def combinationSum(self, candidates, target):
            :type candidates: List[int]
            :type target: int
            :rtype: List[List[int]]
            def back_track(res, nums, i, target, found):
                :list[list[int]], the result 
                :list[int], the candidate 
                :int, the index of current number that needs to be checked
                :int, the remained target
                :list[int], the list of found numbers 
                if target < 0:
                elif target == 0: 
                    res.append(found[:])    # because found is a list (mutable), we must add its copy instead of itself
                    # find the next possible number
                    for j in range(i,n,1):
                        found.append(nums[j])   # try to add it to 'found' list
                        back_track(res, nums, j, target-nums[j], found)
            n = len(candidates)
            # nums = sorted(candidates) # no need in this problem
            nums = candidates
            res = []
            back_track(res, nums, 0, target, [])
            return res

Log in to reply

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