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