Python easy to understand backtracking solution


  • 0
    W

    '''

    class Solution(object):
        def combinationSum2(self, candidates, target):
    
            combis = []
            candidates.sort()
    
            todo = [(target, 0, [])]
            while todo:
                rest, i, combi = todo.pop()
                if rest == 0:
                    combis.append(combi)
                if i < len(candidates) and rest < candidates[i]:
                    continue
    
                already = {}
                while i < len(candidates) and rest >= candidates[i]:
                    if candidates[i] not in already:
                        already[candidates[i]] = 1
                        todo.append((rest-candidates[i], i+1, combi+[candidates[i]]))
                    i += 1
    
            return combis
    

    '''


  • 0
    W

    the 'already' dict is to make sure: in one big while loop, the candidates elements with same value after the combi[-1] can only be added once.

    E.g., candidates = [1,1,2,2,2,2,5,6], target = 10
    while combi = [1,2,2], the elements after the combi[-1] are [2,2,5,6], but 2 can only be added once so the new combi in the next todo while should be [1,2,2,2], [1,2,2,5] and [1,2,2,6].


Log in to reply
 

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