Python 53ms recursion solution with comments


  • 0
    J

    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]]
            """
            
            candidates.sort()
            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:
                            candidates2.remove(j)
                            self.solution.append(res+ [i, j]) # add new resolution
                            helper(candidates2, i, j, res + [i])
                        else:
                            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:
                self.solution.append([target])
            
            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.