# Python DP ~quadratic, simple explanation & 10 line solution

• ### 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 i for every 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 !

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