377. 组合总和 Ⅳ Medium
给你一个由 不同 整数组成的数组 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
解题思路
输入： 一个不同整数数组 nums，一个目标整数 target
输出： 返回总和为 target 的元素组合个数
本题属于线性DP问题。
1. 将问题抽象成动态规划问题
这题是求：用数组 nums 中的数，组成和为 target 的组合个数，顺序不同算不同组合。
- 总目标
target可以由target - num组合出来；
2. 状态定义
令 dp[i] 表示组成整数 i 的组合总数（顺序不同算不同）
3. 状态转移方程
目标是 dp[i]，它可以由前面所有 dp[i - num] 过来：
- 如果你想用
num组成i，那么i - num就必须已经有一个合法组合； - 每个 num 都可以尝试添加到组合最后；
所以：dp[i] = dp[i - num1] + dp[i - num2] + ...（只加能让 i - num ≥ 0 的）
4. 初始条件
python
dp[0] = 1 # 因为组成 0 只有一种方法就是什么都不选5. 目标值
最终答案是 dp[target]
代码实现
python
class Solution:
def combinationSum4(self, nums, target):
# 初始化 dp 数组，dp[i] 表示凑出和为 i 的组合数
dp = [0] * (target + 1)
# 凑出和为 0 的组合数为 1（即什么都不选）
dp[0] = 1
# 遍历从 1 到 target 的每个和
for i in range(1, target + 1):
# 尝试使用 nums 中的每个数字
for num in nums:
# 如果当前目标和 i 大于等于 num，说明可以用 num 来凑
if i >= num:
# dp[i] 加上使用 num 后剩余和 (i - num) 的组合数
dp[i] += dp[i - num]
# 返回凑出目标和 target 的组合数
return dp[target]javascript
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var combinationSum4 = function(nums, target) {
const dp = Array(target + 1).fill(0);
dp[0] = 1;
for (let i = 1; i < target + 1; i++) {
for (let num of nums) {
if (i >= num) {
dp[i] += dp[i - num];
}
}
}
return dp[target];
};复杂度分析
时间复杂度：O(n * target)
空间复杂度：O(target)