### The idea

Let *w(n)* be the number of ways to make *n* using a set of number *nums*.

- The number of ways to make
*n*is the sum of the number of ways to make*n***ending with**for every*i**i*in*nums*. - The number of ways to make
*n*ending with*i*is*w(n-i)*: just sum up to*n-i*then add*i*.

In short, this sums up (pun intended) to:

*w(n)* = sum of *w(n-i)* for *i* in *nums*

### The code

In Python, this translates to:

```
def combinationSum4(nums, target):
n, dp = 1, [1]
nums.sort()
while n <= target:
ans = 0
for i in nums:
if i > n: break
ans += dp[n - i]
dp.append(ans)
n += 1
return dp[target]
```

Let *n* = `target`

and *m* = `len(nums)`

The complexity is *O(n*min(n,m) + mlog(m))*. At the time of writing, this solution beated 100% with 39ms. I believe this optimal.

#### Bonus

As a side note, if *nums* = *{1, 2, ..., n-1}* then *w(n)* = *2^(n-1)-1*, which is the *(n-1)th* Mercenne number.

In python this would look like this:

```
def combinaisonsTo(target): # if nums = [1, ... target-1]
return (1 << target - 1) - 1
```

EDIT: Math $$nope$$ did not work although it is said that it does, I will update this to real maths if leetcode answers my bug report !