摘要

今天要聊的题是 LeetCode 第 377 题 —— 组合总和 Ⅳ。
这道题看起来跟常见的“背包问题”有点像，但有一个关键区别：顺序不同的组合也算不同解法。

比如 [1, 2, 3] 组成目标 4：

• (1, 3) 和 (3, 1) 在这里是两个不同的解法。
  这就让问题更有意思了，因为排列的顺序影响最终的组合数。

在这篇文章里，我会从题目拆解，到动态规划思路，再到 Swift 实现和实际应用场景，为你全面讲清楚这道题。

描述

题目要求：

• 给定一个由 不同整数 构成的数组 nums。
• 再给定一个目标整数 target。
• 我们要计算用 nums 中的数字，按不同顺序组合起来正好等于 target 的方案数。

注意：

• 组合里的数字可以重复使用。
• 顺序不同算作不同的解法。

例子：

• 输入：nums = [1, 2, 3], target = 4
  输出：7
  解法包括：

  (1,1,1,1)
  (1,1,2)
  (1,2,1)
  (2,1,1)
  (2,2)
  (1,3)
  (3,1)
  

题解答案

这道题的核心其实是 动态规划。
为什么？因为组合数是由子问题累加得来的。

比如我们要求 target = 4 的解法数：

• 如果最后一步选择了 1，那剩下的子问题就是 target = 3；
• 如果最后一步选择了 2，那剩下的子问题就是 target = 2；
• 如果最后一步选择了 3，那剩下的子问题就是 target = 1。

所以我们可以写成一个状态转移公式：

dp[i] = Σ(dp[i - num])   对于所有 num ∈ nums，且 i - num >= 0

这里 dp[i] 表示：组成数字 i 的所有组合数量。
最终答案就是 dp[target]。

题解代码分析

下面是 Swift 的实现：

import Foundation

class Solution {
    func combinationSum4(_ nums: [Int], _ target: Int) -> Int {
        var dp = Array(repeating: 0, count: target + 1)
        dp[0] = 1  // base case：组成 0 的方式只有一种，就是不选任何数字
        
        for i in 1...target {
            for num in nums {
                if i - num >= 0 {
                    dp[i] += dp[i - num]
                }
            }
        }
        
        return dp[target]
    }
}

代码解析

1. 初始化

   • dp[0] = 1，因为组成 0 只有一种方式：不选任何数。
   • 这一步是动态规划的基础条件。

2. 状态转移

   • 外层循环 i 遍历目标和。
   • 内层循环遍历 nums 中的每一个数。
   • 如果 i - num >= 0，说明当前数 num 可以被选择，就把 dp[i - num] 的组合数加到 dp[i] 上。

3. 结果

   • 遍历完成后，dp[target] 就是答案。

示例测试及结果

来跑几个测试看看效果：

let solution = Solution()

print(solution.combinationSum4([1, 2, 3], 4))
// 输出: 7

print(solution.combinationSum4([9], 3))
// 输出: 0

print(solution.combinationSum4([2, 5, 7], 10))
// 输出: 3
// 解释: (2,2,2,2,2), (5,5), (2,2,2,2,2)

结果输出：

7
0
3

和预期完全一致。

时间复杂度

• 外层循环遍历 1...target，执行 target 次。
• 内层循环遍历 nums，执行 nums.count 次。
  因此总的时间复杂度是 O(target × n)，其中 n 是数组 nums 的长度。

空间复杂度

• 我们只用到了一个大小为 target + 1 的数组 dp。
• 所以空间复杂度是 O(target)。

总结

这道题最大的特点就是 顺序不同算不同解法，这是和普通“组合问题”的最大区别。
动态规划的思路非常适合，因为它能把复杂的组合问题，分解成一个个小目标，再逐步累加。

实际场景里，这种问题就像是“拼装积木”：

• 目标高度是 target，每个积木的高度是 nums 中的元素。
• 我们要问：有多少种不同的搭积木方式，能刚好拼到目标高度？
• 顺序不同的积木堆叠，也算不同的搭法。