LeetCode 216.组合总和 III：回溯算法实现与剪枝优化

目录

1. 问题描述
2. 解决思路
   • 回溯法
   • 剪枝优化
3. 代码实现
4. 复杂度分析
5. 示例测试
6. 总结与扩展

---

1. 问题描述

给定两个整数 k 和 n，要求找出所有满足以下条件的组合：

• 组合包含 k 个不同的数字。
• 组合中数字的和等于 n。
• 组合中的数字范围为 [1, 9]，且每个数字只能使用一次。

示例：

• 输入：k = 3, n = 7
• 输出：[[1, 2, 4]]
• 解释：1 + 2 + 4 = 7，且没有其他满足条件的三元组。

---

2. 解决思路

2.1 回溯法

回溯法是解决组合问题的经典方法。其核心思想是：

1. 递归生成候选解：从候选数字中逐个尝试添加元素。
2. 剪枝：当发现当前路径无法生成有效解时，提前终止递归。
3. 回溯撤销选择：在递归返回后，撤销最后一步选择，尝试其他可能性。

2.2 剪枝优化

为了提升算法效率，需要设计剪枝条件：

1. 总和超过目标值：若当前路径的和已超过 n，停止递归。
2. 剩余数字不足：若剩余可选的数字不足以填满组合的剩余位置，停止递归。
3. 避免重复组合：按升序选择数字，确保组合唯一。例如，选择 [1, 2, 4] 后不会生成 [2, 1, 4]。

---

3. 代码实现

import java.util.ArrayList;
import java.util.List;class Solution {public List<List<Integer>> combinationSum3(int k, int n) {List<List<Integer>> result = new ArrayList<>();backtrack(result, new ArrayList<>(), 1, k, n, 0);return result;}private void backtrack(List<List<Integer>> result,List<Integer> path,int start,int k,int n,int currentSum) {// 终止条件：路径长度等于kif (path.size() == k) {if (currentSum == n) {result.add(new ArrayList<>(path));}return;}// 计算当前可以选择的数字的最大起始值int remaining = k - path.size();int maxPossible = 10 - remaining; // 确保剩余数字足够填充剩余位置maxPossible = Math.min(maxPossible, 9); // 不超过9for (int i = start; i <= maxPossible; i++) {// 剪枝：总和超过n时提前终止if (currentSum + i > n) break;path.add(i);backtrack(result, path, i + 1, k, n, currentSum + i); // 递归下一层path.remove(path.size() - 1); // 回溯撤销选择}}
}

关键代码解释

• backtrack 方法参数：

  • result：存储所有合法组合的结果集。
  • path：当前递归路径上的数字组合。
  • start：当前可选的起始数字（避免重复）。
  • k, n：题目输入的条件。
  • currentSum：当前路径的数字和。

• 剪枝条件：

  • maxPossible = 10 - remaining：确保剩余的数字足够填充组合的剩余位置。例如，若还需选2个数字，则起始数字最大为 8（因为 8, 9 是最后两个可选数字）。

---

4. 复杂度分析

• 时间复杂度：最坏情况下需要遍历所有组合，时间复杂度为 O(C(9, k))，即从9个数字中选k个的组合数。
• 空间复杂度：递归调用栈深度为 k，空间复杂度为 O(k)。

---

5. 示例测试

示例 1

输入：k = 3, n = 7
输出：[[1, 2, 4]]

示例 2

输入：k = 4, n = 1
输出：[]
解释：无法找到4个不同的数且和为1。

---

6. 总结与扩展

• 回溯法的适用性：适合解决组合、排列、子集等问题，通过递归和剪枝平衡效率。
• 剪枝优化的重要性：合理剪枝可以显著减少无效递归路径。
• 扩展问题：
  • 组合总和 I（数字可重复使用）
  • 组合总和 II（包含重复数字但不可重复使用）

核心收获：通过升序选择数字避免重复，通过预计算最大起始值减少无效遍历。