Python: fast solution using dynamic programming and backtracking

  • 0
    class Solution(object):
        def combinationSum(self, nums, target):
            combinations = set()
            for t in xrange(1, target + 1):
                for n in nums:
                    if t == n or (t - n) in combinations:
            results = []
            partials = [(target, [])]
            while partials:
                newpartials = []
                for t, lst in partials:
                        last = lst[-1]
                    except IndexError:
                        last = -1
                    for n in nums:
                        if n < last:
                        if t == n:
                            results.append(lst + [n])
                        elif (t - n) in combinations:
                            partials.append((t - n, lst + [n]))
                partials = newpartials
            return results

    That code ran in 80 ms, and is the fastest solution so far (although timings are very inaccurate, subject to great fluctuations and should not be trusted).

    If T is the target, C is the set of numbers and S is the set of solutions:

    • the first for loop is O(T |C|) time and O(T) space;
    • the while loop is O(|S|) time and O(|S|) space.

    If I'm not mistaken, the size of the solution set is |S| = O(T |C|).

    Please, could you tell me if I did any mistake when calculating the space/time complexities?


Log in to reply

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