Python iterative solution

  • 0
    class Solution:
        # @param candidates, a list of integers
        # @param target, integer
        # @return a list of lists of integers
        def combinationSum2(self, candidates, target):
            subs = [[]]
            result = []
            for i in xrange(len(candidates)):
                if candidates[i] > target:
                elif candidates[i] == target:
                    if i > 0 and candidates[i] == candidates[i-1]:
                        start = last_len
                        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

    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):
            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]]))
                        if sum == target:
                            combinations.append(combination + [candidates[index]])
                        # no need to try any more
            return combinations

Log in to reply

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