377. 组合总和 Ⅳ - Combination Sum IV

🎯 问题描述（来源于LeetCode）

描述：
给你一个由不同整数组成的数组 nums 和一个目标整数 target。请你从 nums 中找出并返回总和为 target 的元素组合的个数。
题目数据保证答案符合 32 位整数范围。

说明：

  • 顺序不同的序列被视作不同的组合（即排列）。
  • 每个元素可以使用无限次。

示例：

  • 示例 1：
1
2
3
4
5
6
7
8
9
10
输入: 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：
1
2
输入: nums = [9], target = 3
输出: 0

💻 解题思路

思路：动态规划（爬楼梯思想）

算法步骤

  1. 定义 dp[i] 表示总和为 i 的组合个数。
  2. 初始化 dp[0] = 1（空组合）。
  3. 对于 i 从 1 到 target：
    • 遍历 nums 中的每个数字 k，如果 k <= i，则 dp[i] += dp[i - k]（相当于用数字 k 作为最后一步）。
  4. 返回 dp[target]。

代码实现

1
2
3
4
5
6
7
8
9
from typing import List

class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        dp = [1] + [0] * target
        for i in range(1, target + 1):
            # 可将 nums 里的值看作是爬楼梯的步距
            dp[i] = sum(dp[i - k] for k in nums if k <= i)
        return dp[target]

📊 性能分析

  • 时间复杂度：O(target×len(nums))O(target \times len(nums))。
  • 空间复杂度：O(target)O(target)。

思考

本题本质是求排列数（顺序相关），与 LeetCode 518 题（零钱兑换 II，组合数）不同。动态规划的顺序（外层遍历 target，内层遍历 nums）保证了不同顺序被统计为不同组合。用户代码思路清晰，使用了类似爬楼梯的递推关系，是正确的解法。注意：当 target 较大时，结果可能超过 32 位整数范围，但题目保证不会溢出。