Python: fast solution using dynamic programming and backtracking


  • 0
    G
    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:
                        combinations.add(t)
                        break
            
            results = []
            partials = [(target, [])]
            
            while partials:
                newpartials = []
                
                for t, lst in partials:
                    try:
                        last = lst[-1]
                    except IndexError:
                        last = -1
                    for n in nums:
                        if n < last:
                            continue
                        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?

    Thanks!


Log in to reply
 

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