Python iterative solution


  • 0
    L
    class Solution:
        # @param candidates, a list of integers
        # @param target, integer
        # @return a list of lists of integers
                
        def combinationSum2(self, candidates, target):
            candidates.sort()
            subs = [[]]
            result = []
            for i in xrange(len(candidates)):
                if candidates[i] > target:
                    break
                elif candidates[i] == target:
                    result.append([target])
                    break
                else:
                    if i > 0 and candidates[i] == candidates[i-1]:
                        start = last_len
                    else:
                        start = 0
                    last_len = len(subs)
                    for j in xrange(start, len(subs)):
                        value = sum(subs[j]) + candidates[i]
                        if value == target:
                            result.append(subs[j] + [candidates[i]])
                        elif value < target:
                            subs.append(subs[j] + [candidates[i]])
                    
            
            return result
    

    The above-shared solution can be further optimized. For example, if [1,2,3] + candidates[i] > target, then [1,2,3] should be removed, considering candidates[i+1] >= candidates[i], as a result, we can reduce calculation time.

    But removing item from list which is not the last one wastes much time. Maybe list is a good solution. I will try it.


  • 0
    D

    I have come up with a simpler iterative version, inspired by the post "Simple and fast DFS solution, python AC 98ms" in for Combination Sum. The idea is to push the total of current combination and start index onto stack. Thus there is no need to calculate sum of current combination and the tricky handling of start index

    class Solution:
        # @param {integer[]} candidates
        # @param {integer} target
        # @return {integer[][]}
        def combinationSum2(self, candidates, target):
            candidates.sort()
            combinations, stack = [], [(0, 0, [])]
            while stack:
                (total, start, combination) = stack.pop()
                for index in range(start, len(candidates)):
                    sum = total + candidates[index]
                    if sum < target:
                        if (index == start) or (candidates[index] != candidates[index-1]):
                            # avoid duplicates
                            stack.append((sum, index+1, combination + [candidates[index]]))
                    else:
                        if sum == target:
                            combinations.append(combination + [candidates[index]])
                        # no need to try any more
                        break
            return combinations
    

Log in to reply
 

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