# DP solution in Python

• I also did it with recursion, turns out the DP solution is 3~4 times faster.

``````def combinationSum2(self, candidates, target):
candidates.sort()
table = [None] + [set() for i in range(target)]
for i in candidates:
if i > target:
break
for j in range(target - i, 0, -1):
table[i + j] |= {elt + (i,) for elt in table[j]}
return map(list, table[target])``````

• I am wondering what if I give you a input like : candidates: {1,2,3}, target: 2147483647. or any other targets which are very large.

• you are right, when the target is huge it takes a lot of memory with no good use!

• Neat! But I do not think this is DP enough(?) Cause there are no clear sub problems solved before the larger problems. Eg. For each iteration, this alg. updates multiple result sets. And only until the program terminated can we finally and safely get the table[target].

• Do we need to sort here? what is its purpose?

• Good solution. I got a cleaner version here.

``````class Solution(object):
def combinationSum2(self, candidates, target):
candidates.sort()
dp = [set() for i in xrange(target+1)]
for num in candidates:
for t in xrange(target, num-1, -1):
for prev in dp[t-num]:
For the uninitiated, basically, this problem is a variant of the knapsack problem. If you can understand the solution to Coin Change or Coin Change 2, then you can easily understand this solution. One caveat here is that the inner loop is reversed `for t in xrange(target, num-1, -1)`, because each number can only be used once.