LeetCode 377 组合总和 Ⅳ

在这里插入图片描述

文章目录

- 摘要
- 描述
- 题解答案
- 题解代码分析
- - 1. 动态规划的基本思路
    - 2. 初始状态
    - 3. 状态转移方程
    - 4. 为什么这样能计算出排列个数？
    - 5. 与组合问题的区别
    - 6. 优化：避免不必要的计算
- 示例测试及结果
- - 示例 1：nums = [1,2,3], target = 4
    - 示例 2：nums = [9], target = 3
    - 示例 3：nums = [1,2], target = 3
    - 示例 4：nums = [1], target = 1
- 时间复杂度
- 空间复杂度
- 进阶问题：如果数组中含有负数
- - 问题分析
    - 解决方案
- 实际应用场景
- - 场景一：零钱兑换问题
    - 场景二：爬楼梯问题
    - 场景三：路径计数问题
    - 场景四：背包问题
- 总结

摘要

这道题其实挺有意思的，它让我们找出所有可能的排列方式，使得这些数字的和等于目标值。虽然题目名字叫"组合总和"，但实际上这是一道排列问题，因为顺序不同的序列被视为不同的组合。比如 (1, 2) 和 (2, 1) 被视为两种不同的方式。

这道题本质上是一个动态规划问题，我们可以用动态规划来高效地解决它。今天我们就用 Swift 来搞定这道题，顺便聊聊动态规划在实际开发中的应用场景。

描述

题目要求是这样的：给你一个由不同整数组成的数组 nums，和一个目标整数 target。请你从 nums 中找出并返回总和为 target 的元素排列的个数。

题目数据保证答案符合 32 位整数范围。

示例 1：

1输入：nums = [1,2,3], target = 4
2输出：7
3解释：
4所有可能的组合为：
5(1, 1, 1, 1)
6(1, 1, 2)
7(1, 2, 1)
8(1, 3)
9(2, 1, 1)
10(2, 2)
11(3, 1)
12

请注意，顺序不同的序列被视作不同的组合。比如 (1, 1, 2) 和 (1, 2, 1) 被视为两种不同的方式。

示例 2：

1输入：nums = [9], target = 3
2输出：0
3

提示：

1 <= nums.length <= 200
1 <= nums[i] <= 1000
nums 中的所有元素互不相同
1 <= target <= 1000

这道题的核心思路是什么呢？其实这是一道动态规划问题。我们可以用 dp[i] 表示和为 i 的排列个数。对于每个 i，我们遍历 nums 中的每个数 num，如果 i >= num，那么 dp[i] 就可以从 dp[i - num] 转移过来。这样我们就能计算出所有可能的排列个数。

题解答案

下面是完整的 Swift 解决方案：

1class Solution {
2    func combinationSum4(_ nums: [Int], _ target: Int) -> Int {
3        // dp[i] 表示和为 i 的排列个数
4        var dp = Array(repeating: 0, count: target + 1)
5        
6        // 初始状态：和为 0 的排列个数为 1（空排列）
7        dp[0] = 1
8        
9        // 遍历每个可能的和
10        for i in 1...target {
11            // 遍历 nums 中的每个数
12            for num in nums {
13                // 如果当前和 i 大于等于 num，可以从 dp[i - num] 转移过来
14                if i >= num {
15                    dp[i] += dp[i - num]
16                }
17            }
18        }
19        
20        return dp[target]
21    }
22}
23

题解代码分析

让我们一步步分析这个解决方案：

1. 动态规划的基本思路

动态规划的核心思想是：将大问题分解成小问题，通过解决小问题来解决大问题。在这道题中，我们要计算和为 target 的排列个数，可以将其分解为：对于每个可能的和 i，计算和为 i 的排列个数。

1var dp = Array(repeating: 0, count: target + 1)
2

我们创建一个数组 dp，其中 dp[i] 表示和为 i 的排列个数。数组大小为 target + 1，因为我们需要计算从 0 到 target 的所有可能和。

2. 初始状态

1dp[0] = 1
2

初始状态是：和为 0 的排列个数为 1。这对应空排列的情况，即不选任何数字。这个初始状态很重要，因为它是所有其他状态的基础。

3. 状态转移方程

1for i in 1...target {
2    for num in nums {
3        if i >= num {
4            dp[i] += dp[i - num]
5        }
6    }
7}
8

这是核心的状态转移过程。对于每个可能的和 i（从 1 到 target），我们遍历 nums 中的每个数 num：

如果 i >= num，说明我们可以用 num 来组成和为 i 的排列
如果我们选择了 num，那么剩下的和就是 i - num
所以 dp[i] 应该加上 dp[i - num]，表示所有和为 i - num 的排列都可以通过加上 num 来得到和为 i 的排列

注意，这里我们遍历 nums 的顺序很重要。因为题目要求的是排列（顺序不同视为不同），所以我们需要考虑所有可能的顺序。通过先遍历 i，再遍历 nums，我们确保了所有可能的排列都被计算到了。

4. 为什么这样能计算出排列个数？

让我们用一个例子来说明。假设 nums = [1, 2, 3]，target = 4：

dp[0] = 1（空排列）
dp[1]：可以用 1 组成，dp[1] = dp[0] = 1（只有一种方式：(1)）
dp[2]：
- 可以用 1 组成：dp[2] += dp[1] = 1（(1, 1)）
- 可以用 2 组成：dp[2] += dp[0] = 1（(2)）
- 所以 dp[2] = 2
dp[3]：
- 可以用 1 组成：dp[3] += dp[2] = 2（(1, 1, 1), (1, 2)）
- 可以用 2 组成：dp[3] += dp[1] = 1（(2, 1)）
- 可以用 3 组成：dp[3] += dp[0] = 1（(3)）
- 所以 dp[3] = 4
dp[4]：
- 可以用 1 组成：dp[4] += dp[3] = 4（(1, 1, 1, 1), (1, 1, 2), (1, 2, 1), (1, 3)）
- 可以用 2 组成：dp[4] += dp[2] = 2（(2, 1, 1), (2, 2)）
- 可以用 3 组成：dp[4] += dp[1] = 1（(3, 1)）
- 所以 dp[4] = 7

可以看到，通过这种方式，我们计算出了所有可能的排列个数。

5. 与组合问题的区别

这道题虽然名字叫"组合总和"，但实际上是一道排列问题。如果是组合问题，我们只需要考虑数字的选择，不需要考虑顺序。但这里是排列问题，顺序不同的序列被视为不同的组合。

在代码中，我们通过先遍历 i，再遍历 nums 来确保所有可能的顺序都被考虑到了。如果我们先遍历 nums，再遍历 i，那就变成了组合问题，顺序不同的序列会被视为相同的组合。

6. 优化：避免不必要的计算

虽然题目没有要求，但我们可以做一些优化。比如，如果 nums 中有很多大于 target 的数，我们可以先过滤掉它们：

1class Solution {
2    func combinationSum4(_ nums: [Int], _ target: Int) -> Int {
3        // 过滤掉大于 target 的数
4        let validNums = nums.filter { $0 <= target }
5        
6        var dp = Array(repeating: 0, count: target + 1)
7        dp[0] = 1
8        
9        for i in 1...target {
10            for num in validNums {
11                if i >= num {
12                    dp[i] += dp[i - num]
13                }
14            }
15        }
16        
17        return dp[target]
18    }
19}
20

不过对于这道题，由于 nums[i] <= 1000 且 target <= 1000，这个优化可能不会带来明显的性能提升。

示例测试及结果

让我们用几个例子来测试一下这个解决方案：

示例 1：nums = [1,2,3], target = 4

1let solution = Solution()
2let result1 = solution.combinationSum4([1,2,3], 4)
3print("示例 1 结果: \(result1)")  // 输出: 7
4

执行过程分析：

初始化：dp = [1, 0, 0, 0, 0]
i = 1：
- num = 1：dp[1] += dp[0] = 1
- num = 2：1 >= 2 不成立，跳过
- num = 3：1 >= 3 不成立，跳过
- dp[1] = 1
i = 2：
- num = 1：dp[2] += dp[1] = 1
- num = 2：dp[2] += dp[0] = 1
- num = 3：2 >= 3 不成立，跳过
- dp[2] = 2
i = 3：
- num = 1：dp[3] += dp[2] = 2
- num = 2：dp[3] += dp[1] = 1
- num = 3：dp[3] += dp[0] = 1
- dp[3] = 4
i = 4：
- num = 1：dp[4] += dp[3] = 4
- num = 2：dp[4] += dp[2] = 2
- num = 3：dp[4] += dp[1] = 1
- dp[4] = 7

所有可能的排列：

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

总共 7 种方式。

示例 2：nums = [9], target = 3

1let result2 = solution.combinationSum4([9], 3)
2print("示例 2 结果: \(result2)")  // 输出: 0
3

执行过程分析：

初始化：dp = [1, 0, 0, 0]
i = 1：1 >= 9 不成立，dp[1] = 0
i = 2：2 >= 9 不成立，dp[2] = 0
i = 3：3 >= 9 不成立，dp[3] = 0

因为 nums 中只有 9，而 9 > 3，所以无法组成和为 3 的排列，结果为 0。

示例 3：nums = [1,2], target = 3

1let result3 = solution.combinationSum4([1,2], 3)
2print("示例 3 结果: \(result3)")  // 输出: 3
3

执行过程分析：

初始化：dp = [1, 0, 0, 0]
i = 1：
- num = 1：dp[1] += dp[0] = 1
- dp[1] = 1
i = 2：
- num = 1：dp[2] += dp[1] = 1
- num = 2：dp[2] += dp[0] = 1
- dp[2] = 2
i = 3：
- num = 1：dp[3] += dp[2] = 2
- num = 2：dp[3] += dp[1] = 1
- dp[3] = 3

所有可能的排列：

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

总共 3 种方式。

示例 4：nums = [1], target = 1

1let result4 = solution.combinationSum4([1], 1)
2print("示例 4 结果: \(result4)")  // 输出: 1
3

执行过程分析：

初始化：dp = [1, 0]
i = 1：
- num = 1：dp[1] += dp[0] = 1
- dp[1] = 1

所有可能的排列：

总共 1 种方式。

时间复杂度

这个算法的时间复杂度是 O(target × n)，其中 target 是目标值，n 是 nums 数组的长度。

为什么是 O(target × n)？

外层循环遍历 i 从 1 到 target，共 target 次
内层循环遍历 nums 中的每个数，共 n 次
每次循环的操作都是 O(1) 的

所以总时间复杂度是 O(target × n)。

对于这道题，target <= 1000，n <= 200，所以最坏情况下需要 200,000 次操作，这在现代计算机上是非常快的。

空间复杂度

这个算法的空间复杂度是 O(target)。

为什么是 O(target)？

我们使用了一个大小为 target + 1 的数组 dp 来存储中间结果。除了这个数组，我们没有使用额外的空间，所以空间复杂度是 O(target)。

对于这道题，target <= 1000，所以空间复杂度是可以接受的。

进阶问题：如果数组中含有负数

题目提到了一个进阶问题：如果给定的数组中含有负数会发生什么？问题会产生何种变化？如果允许负数出现，需要向题目中添加哪些限制条件？

问题分析

如果 nums 中含有负数，会出现以下问题：

无限循环：如果 nums 中有正数和负数，且它们的和可以抵消，那么可能存在无限多种排列方式。比如 nums = [1, -1]，target = 0，我们可以用任意多个 (1, -1) 对来组成和为 0 的排列。
状态转移变得复杂：原来的状态转移方程 dp[i] += dp[i - num] 在 num 为负数时仍然成立，但需要确保 i - num 在有效范围内。
需要限制条件：为了避免无限循环，我们需要添加一些限制条件，比如：
- 限制排列的长度（最多使用 k 个数字）
- 限制每个数字的使用次数
- 要求排列中正数和负数的数量相等

解决方案

如果允许负数出现，我们可以这样修改代码：

1class Solution {
2    func combinationSum4(_ nums: [Int], _ target: Int, maxLength: Int = 1000) -> Int {
3        // 如果 nums 中有负数，需要限制排列的最大长度
4        var dp = Array(repeating: 0, count: target + 1)
5        dp[0] = 1
6        
7        // 使用二维 DP：dp[i][j] 表示用 j 个数字组成和为 i 的排列个数
8        var dp2D = Array(repeating: Array(repeating: 0, count: maxLength + 1), count: target + 1)
9        dp2D[0][0] = 1
10        
11        for i in 0...target {
12            for j in 0..<maxLength {
13                for num in nums {
14                    let nextSum = i + num
15                    if nextSum >= 0 && nextSum <= target {
16                        dp2D[nextSum][j + 1] += dp2D[i][j]
17                    }
18                }
19            }
20        }
21        
22        // 返回所有长度的排列个数之和
23        var result = 0
24        for j in 0...maxLength {
25            result += dp2D[target][j]
26        }
27        
28        return result
29    }
30}
31

不过这个解决方案比较复杂，而且对于原题（没有负数）来说是不必要的。

实际应用场景

动态规划在实际开发中的应用非常广泛。让我们看看几个常见的应用场景：

场景一：零钱兑换问题

这是一个经典的动态规划问题，和这道题非常相似：

1func coinChange(_ coins: [Int], _ amount: Int) -> Int {
2    var dp = Array(repeating: Int.max, count: amount + 1)
3    dp[0] = 0
4    
5    for i in 1...amount {
6        for coin in coins {
7            if i >= coin && dp[i - coin] != Int.max {
8                dp[i] = min(dp[i], dp[i - coin] + 1)
9            }
10        }
11    }
12    
13    return dp[amount] == Int.max ? -1 : dp[amount]
14}
15

这个问题是求最少需要多少个硬币，而我们的问题是求有多少种排列方式。

场景二：爬楼梯问题

爬楼梯问题也可以用类似的思路解决：

1func climbStairs(_ n: Int) -> Int {
2    if n <= 2 {
3        return n
4    }
5    
6    var dp = Array(repeating: 0, count: n + 1)
7    dp[1] = 1
8    dp[2] = 2
9    
10    for i in 3...n {
11        dp[i] = dp[i - 1] + dp[i - 2]
12    }
13    
14    return dp[n]
15}
16

这个问题可以看作是 nums = [1, 2]，target = n 的特殊情况。

场景三：路径计数问题

在网格中，从左上角到右下角有多少种路径：

1func uniquePaths(_ m: Int, _ n: Int) -> Int {
2    var dp = Array(repeating: Array(repeating: 0, count: n), count: m)
3    
4    for i in 0..<m {
5        dp[i][0] = 1
6    }
7    for j in 0..<n {
8        dp[0][j] = 1
9    }
10    
11    for i in 1..<m {
12        for j in 1..<n {
13            dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
14        }
15    }
16    
17    return dp[m - 1][n - 1]
18}
19

场景四：背包问题

完全背包问题也可以用类似的思路解决：

1func knapsack(_ weights: [Int], _ values: [Int], _ capacity: Int) -> Int {
2    var dp = Array(repeating: 0, count: capacity + 1)
3    
4    for i in 1...capacity {
5        for j in 0..<weights.count {
6            if i >= weights[j] {
7                dp[i] = max(dp[i], dp[i - weights[j]] + values[j])
8            }
9        }
10    }
11    
12    return dp[capacity]
13}
14

总结

这道题虽然名字叫"组合总和"，但实际上是一道排列问题。通过动态规划，我们可以高效地计算出所有可能的排列个数。

关键点总结：

理解题意：顺序不同的序列被视为不同的组合，所以这是排列问题
动态规划思路：用 dp[i] 表示和为 i 的排列个数
状态转移：dp[i] = sum(dp[i - num]) for num in nums where i >= num
遍历顺序：先遍历 i，再遍历 nums，确保所有可能的顺序都被考虑到
时间复杂度：O(target × n)
空间复杂度：O(target)

动态规划虽然看起来复杂，但一旦理解了核心思想，就能解决很多类似的问题。在实际开发中，动态规划常用于优化问题、计数问题等场景。

《LeetCode 377 组合总和 Ⅳ》是转载文章，点击查看原文。