题目描述：

LeetCode 377题 “Combination Sum IV” 是一个关于组合数学的动态规划问题。题目要求给定一个由正整数组成的数组 nums 和一个目标值 target，找出所有可能的组合，使得这些组合中的数字之和等于 target。每个数字在组合中可以无限次使用，但组合中的顺序不同的序列被认为是不同的组合。

示例：

输入: 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)

解题思路：

这个问题可以通过动态规划来解决。我们定义一个数组 dp，其中 dp[i] 表示和为 i 的组合数。初始时，dp[0] = 1，因为和为0的组合只有一种，即什么也不选。

接下来，我们遍历从1到target的每一个数，对于每一个数i，我们再遍历nums数组中的每一个数num，如果i >= num，则dp[i] += dp[i - num]。这是因为如果我们可以通过某种方式组合出i - num，那么再加上num就可以组合出i。

代码实现：

def combinationSum4(nums, target):

dp = [0] * (target + 1)
# 和为0的组合只有一种，即什么也不选
dp[0] = 1

# 遍历从1到target的每一个数
for i in range(1, target + 1):
    # 遍历nums数组中的每一个数
    for num in nums:
        # 如果当前数i大于等于num，则更新dp[i]
        if i >= num:
            dp[i] += dp[i - num]

# 返回和为target的组合数
return dp[target]

nums = [1, 2, 3] target = 4 print(combinationSum4(nums, target)) # 输出: 7

详细解释：

1. 初始化dp数组：
   • dp数组的大小为target + 1，因为我们需要计算从0到target的所有可能的组合数。
   • dp[0] = 1是因为和为0的组合只有一种，即什么也不选。
2. 外层循环：
   • 遍历从1到target的每一个数i，表示我们当前要计算和为i的组合数。
3. 内层循环：
   • 遍历nums数组中的每一个数num，表示我们尝试使用num来组合出和为i的情况。
   • 如果i >= num，说明我们可以使用num来组合出和为i的情况，此时dp[i]应该加上dp[i - num]，因为dp[i - num]表示和为i - num的组合数，加上num后就能组合出和为i的情况。
4. 返回结果：
   • 最终dp[target]就是我们要求的和为target的组合数。

时间复杂度：

• 时间复杂度为O(target * n)，其中n是nums数组的长度。这是因为我们需要遍历从1到target的每一个数，并且对于每一个数，我们还需要遍历nums数组中的每一个数。

空间复杂度：

• 空间复杂度为O(target)，因为我们使用了一个长度为target + 1的数组来存储中间结果。

通过上述分析和代码实现，我们可以有效地解决LeetCode 377题 “Combination Sum IV”。