难度: 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
提示：
1 <= nums.length <= 2001 <= nums[i] <= 1000nums 中的所有元素 互不相同1 <= target <= 1000
进阶：如果给定的数组中含有负数会发生什么？问题会产生何种变化？如果允许负数出现，需要向题目中添加哪些限制条件？
运行时间: 23 ms
内存: 15.9 MB
class Solution:
def combinationSum4(self, nums: List[int], target: int) -> int:
dp = [0]*(target+1)
dp[0]=1
for i in range(1,target+1):
for num in nums:
if i>=num:
dp[i] += dp[i-num]
return dp[-1]
这个题解使用动态规划的思路来解决问题。我们定义 dp[i] 表示组合成目标数 i 的组合数。对于每个目标数 i，我们枚举数组中的每个数 num，如果 i >= num，则将 dp[i] 的值增加 dp[i-num]，因为如果我们能组合成 i-num，那么加上 num 就能组合成 i。最终答案即为 dp[target] 的值。
时间复杂度: O(target * n)
空间复杂度: O(target)
class Solution:
def combinationSum4(self, nums: List[int], target: int) -> int:
# 初始化 dp 数组，dp[i] 表示组合成目标数 i 的组合数
dp = [0]*(target+1)
# 组合成目标数 0 的组合数为 1，即空集
dp[0]=1
# 遍历目标数 i 从 1 到 target
for i in range(1,target+1):
# 遍历数组 nums 中的每个数
for num in nums:
# 如果 i >= num，则将 dp[i] 的值增加 dp[i-num]
if i>=num:
dp[i] += dp[i-num]
# 最终答案即为 dp[target] 的值
return dp[-1]
初始化dp[0]为1是因为组合成目标数0的唯一方式是不使用任何数字，即使用一个空集。这种情况在数学和编程中通常被认为是唯一的方法（只有一个空集可以构成0）。这也是一个边界条件，为动态规划提供基础，使得当我们在计算dp[i]时，可以正确计算包括空集在内的所有组合。
这个问题的解法依赖于从小到大计算dp值的顺序，因为每个dp[i]的值依赖于之前的dp值（具体为dp[i-num]，其中num是数组中的数）。如果我们从1到target的顺序计算，可以保证在计算dp[i]时，所有需要的dp[i-num]都已经被计算过且存储好了。如果反向从target到1计算，我们将无法保证在计算dp[i]时dp[i-num]已经准备好，因此无法正确使用先前的计算结果。
在这个特定的动态规划问题中，nums数组的遍历顺序实际上不影响最终计算的结果，只是会影响到dp数组的更新顺序。由于每次更新dp[i]都是基于dp[i-num]的值，不论nums的遍历顺序如何，所有的dp[i]都会被正确计算。然而，对于其他问题（例如最小硬币找零），排序可能对优化有所帮助。在当前问题中，排序nums不会带来计算效率的提升。
如果nums中包含重复元素，当前的动态规划方法仍然适用，因为动态规划的状态转移方程考虑的是通过加上一个nums中的元素达到新的目标数，而不是元素本身的唯一性。重复元素在遍历过程中多次增加相同的值不会影响最终的结果，因为我们关心的是组合的数量而非具体组合。因此，无需调整算法即可处理重复元素。