图片.png
C++:
////这个题递归会TLE 所以不可以
//void helper(vector<int>&nums, int target, int& ans, int curSum) {
// if (curSum == target) {
// ans++;
// return;
// }
// if (curSum > target)
// return;
// for (int i = 0; i < nums.size(); i++) {
// helper(nums, target, ans, curSum + nums[i]);
// }
// return;
//}
//int combinationSum4(vector<int>& nums, int target) {
// int ans = 0;
// helper(nums, target, ans, 0);
// return ans;
//}
//其中dp[i]表示目标数为i的解的个数
int combinationSum4(vector<int>& nums, int target) {
vector<int> dp(target + 1);
dp[0] = 1;
for (int i = 1; i <= target; ++i) {
for (auto a : nums) {
if (i >= a)
dp[i] += dp[i - a];
}
}
return dp.back();
}
