DP method is very clear and simple. It is similar like recursive method.

# code block

```
int combinationSum4(vector<int>& nums, int target) {
int n = nums.size();
vector<int> dp(target+1,0);
dp[0] = 1;
for(int i = 1;i<=target;i++){//for each sub-target, we want to find out the number of combination
for(int num:nums){
if(i>=num){dp[i] = dp[i] + dp[i-num];}
}
}
return dp[target];
}
```

I first used the backtracking method, which is Memory Limit Exceeded when our target goes very large, but if this problem requires you output the combinations, the backtracking method is very useful. (Only for positive number)

# code block

```
int combinationSum4(vector<int>& nums, int target) {
vector<int> path;
vector<vector<int>> res;
find(nums,target,path,res);
return res.size();//or you can change it to output the vector res.
}
void find(vector<int>& nums, int target, vector<int>& path, vector<vector<int>>& res){
if (target == 0) { res.push_back(path); return;}
else if (target < 0 ) return;
for(int i = 0;i<nums.size();i++){
path.push_back(nums[i]);
find(nums, target - nums[i], path, res);
path.pop_back();
}
}
```