题目
给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。
题目数据保证答案符合 32 位整数范围。
示例 1：
输入：nums = [1,2,3], target = 4
输出：7
解释：
所有可能的组合为：
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
请注意，顺序不同的序列被视作不同的组合。
示例 2：
输入：nums = [9], target = 3
输出：0
解题思路
动态规划的方法解决总和为target的元素组合个数的问题。创建一个大小为target+1的数组dp，初始化所有元素为0。dp[i]表示凑齐金额i所需要的元素组合个数。设置初始条件dp[0] = 1，因为凑齐金额为0只有一种组合方式，即不选择任何元素。外层循环遍历目标金额从1到target的所有可能值。内层循环遍历nums数组中的每个元素。对于当前的目标金额i，如果i大于等于nums[j]，说明可以选取当前元素nums[j]，则将dp[i]的值加上dp[i - nums[j]]。这表示已经使用了一个nums[j]，还需要凑齐金额i - nums[j]的元素组合个数。最后返回dp[target]，即凑齐目标金额target所需要的元素组合个数。
代码实现
class Solution {
public:
int combinationSum4(vector<int>& nums, int target) {
vector<unsigned int> dp(target + 1, 0);
dp[0] = 1;
for (int i = 1; i <= target; i++) {
for (int j = 0; j < nums.size(); j++) {
if (i >= nums[j]) {
dp[i] += dp[i - nums[j]];
}
}
}
return dp[target];
}
};