### DP Solution (Accepted, 60 ms):

```
class Solution(object):
def combinationSum4(self, nums, target):
nums.sort()
dp=[0]*(target+1)
dp[0]=1 # if num == target
for i in xrange(1,target+1):
for num in nums:
if num>i:
break
dp[i]+=dp[i-num]
return dp[target]
```

### DFS Solution (Time Limit Exceeded):

DFS solution can only handle small cases(i.e.`target<=25 && len(nums)<=5`

), due to large list memory usage of `combs`

.

```
class Solution(object):
def combinationSum4(self, nums, target):
nums.sort()
path=[]
combs=[]
self.dfs(nums, target, path, combs)
return len(combs)
def dfs(self, nums, target, path, combs):
if target==0:
combs.append(path)
for i in xrange(0,len(nums)):
if nums[i]>target:
break
self.dfs(nums, target-nums[i], path+[nums[i]], combs)
```