Python: fast solution using dynamic programming and backtracking

• ``````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:
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!

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