Python 53ms recursion solution with comments

  • 0

    This should be faster with a better 'pointers' movement strategy (e.g. increments based on candidate elements), especially when the target is large, but the basic idea of the algorithm is already here.

    class Solution(object):
        def combinationSum2(self, candidates, target):
            :type candidates: List[int]
            :type target: int
            :rtype: List[List[int]]
            self.solution = list()
            def helper(candidates, left, right, res):
                i = left # left pointer
                j = right - left # right pointer
                candidates2 = list()
                candidates2[:] = candidates  # copy candidate list
                while i <= j:
                    if i in candidates2:
                        candidates2.remove(i) # remove already used/found candidates, the following recursion calls make sure all possible resolution start with the removed candidate get appended to the solution list.
                        if j in candidates2:
                            self.solution.append(res+ [i, j]) # add new resolution
                            helper(candidates2, i, j, res + [i])
                            helper(candidates2, i, j, res + [i])
                    i += 1 # moving two pointers so that the summation == new target
                    j -= 1
            left = 1
            right = target
            if target in candidates:
            helper(candidates, left, right, [])
            return self.solution

Log in to reply

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