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
forloop is O(T |C|) time and O(T) space;
whileloop 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?