本题发现用dfs是要超时的，看了别人的答案发现是要dp。
- dp[i] 表示target = i 时的组合种数。所以， ans = dp[target].
- dp[i] = sum { dp[i - nums[0]], dp[i - nums[1]], ... , dp[i - nums[sizeOfNums-1]] }
- dp[0] = 1 (理解这个非常重要， 从下面的推导就可以知道为啥dp[0] = 1)
对于nums = {1,2}, target = 3.
- dp[3] = dp[3-1] + dp[3-2] = dp[2] + dp[1]
- dp[2] = dp[2-1] + dp[2-2] = d[1] + dp[0], 之所以这里有个dp[0]是因为nums里有一个大小和2 相等的数，所以相减为0，所以算是一个组合，所以为dp[0] =1.
- dp[1] = dp[0]+dp[-1]，明显负数是不可能达到的，所以dp[负数] = 0。
#include<vector>
#include<algorithm>
#include<cstdio>
#include <unordered_map>
#include <cmath>
using namespace std;
class Solution {
public:
int combinationSum4(vector<int>& nums, int target) {
// ans = dp[target]
vector<int> dp(target + 1);
sort(nums.begin(), nums.end());
int sizeOfNums = (int)nums.size();
//
dp[0] = 1;
for (int i = 1; i <= target; i++)
{
dp[i] = 0;
for (int j = 0; j < sizeOfNums; j++)
{
if (i- nums[j] >= 0)
{
dp[i] += dp[i - nums[j]];
}
else
{
// if i- nums[j] < 0
break;
}
}
}
return dp[target];
}
};
