LeetCode 77. 组合——剪枝从O(C(n,k)*k)到最优的过程
LeetCode 77. 组合——剪枝从O(C(n,k)*k)到最优的过程
适读人群：Java初中级工程师、算法面试备战者 | 阅读时长：约20分钟 | 难度：中等
开篇故事
组合这道题看起来比全排列简单——因为组合不考虑顺序，{1,2,3} 和 {3,2,1} 是同一个组合。但实现上，"保证不重复计算同一个组合"这件事，就需要通过 start 参数来约束"只从前往后选"。
更有意思的是，这道题的剪枝优化非常经典，从朴素回溯到加入"层级剪枝"后，搜索树的节点数可以从 O(2^n) 降到 O(C(n,k))。我第一次看到这个剪枝条件时觉得特别妙：i <= n - (k - path.size()) + 1，这个上界限制了 i 的范围，用语言描述就是"从 i 开始到 n，剩余的元素数量至少要够凑齐还需要的元素数"。
把这个剪枝推导清楚，你会对"剪枝"有全新的认识——它不是靠直觉发现的，而是靠对"搜索树"精确分析推导出来的。
一、题目解析
题目： 给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。你可以按任意顺序返回答案。
示例：
- 输入：n=4, k=2，输出：[[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
- 输入：n=1, k=1，输出：[[1]]
结果数量： C(n,k) = n! / (k! × (n-k)!)。
当 n=20, k=10 时，C(20,10) = 184756，规模不大，但朴素回溯的搜索树有更多节点（包括"走到一半发现选不够 k 个"就失败的分支）。
剪枝的动机：
朴素回溯中，i 从 start 遍历到 n，但当 path 还缺少 need = k - path.size() 个元素时，如果从 i 开始到 n 只剩 n - i + 1 个元素，且 n - i + 1 < need，则无论怎么选都凑不够 k 个，这个分支必然失败，直接跳过。
因此，i 的上限应该是 n - need + 1 = n - (k - path.size()) + 1。
二、解法一：朴素回溯（无剪枝）
代码
import java.util.*;
public class Solution_Basic {
private List<List<Integer>> result = new ArrayList<>();
public List<List<Integer>> combine(int n, int k) {
backtrack(n, k, 1, new ArrayList<>());
return result;
}
private void backtrack(int n, int k, int start, List<Integer> path) {
if (path.size() == k) {
result.add(new ArrayList<>(path));
return;
}
// 从 start 到 n，尝试每个数
for (int i = start; i <= n; i++) {
path.add(i);
backtrack(n, k, i + 1, path);
path.remove(path.size() - 1);
}
}
}搜索树分析（n=5, k=3）
朴素回溯的搜索树有多少节点？
在每层，我们从 [start, n] 中选一个数，path 长度从 0 增长到 k。总节点数 = C(n,0) + C(n,1) + ... + C(n,k) ≈ O(2^n) 的一部分，但包含了很多"注定失败"的节点。
例如，当 path=[5]，start=6，n=5，k=3 时，需要再选2个，但已经没有数可选，进入这个分支是无效的。朴素回溯不会阻止我们进入这些分支。
复杂度分析
- 时间复杂度： O(C(n,k) × k)，共 C(n,k) 个叶子，每个复制需要 O(k)。非叶子节点数量是 C(n,k-1) + C(n,k-2) + ... 总和约 O(C(n,k) × k/n)。
- 空间复杂度： O(k)，递归栈深度最大为 k。
三、解法二：加入剪枝（层级剪枝）
剪枝条件推导
当前 path 已有 path.size() 个元素，还需要 need = k - path.size() 个元素。 当前扫描到下标 i（即1-based的数 i），从 i 到 n 一共有 n - i + 1 个数。
若 n - i + 1 < need，即剩余数不够补齐，该分支不可能成功，直接剪掉。
等价地，有效的 i 的范围：n - i + 1 >= need → i <= n - need + 1 = n - (k - path.size()) + 1。
所以 for 循环的上界从 i <= n 改为 i <= n - (k - path.size()) + 1。
代码
import java.util.*;
public class Solution {
private List<List<Integer>> result = new ArrayList<>();
public List<List<Integer>> combine(int n, int k) {
backtrack(n, k, 1, new ArrayList<>());
return result;
}
private void backtrack(int n, int k, int start, List<Integer> path) {
if (path.size() == k) {
result.add(new ArrayList<>(path));
return;
}
// 剪枝：i 的上界是 n - (k - path.size()) + 1
// 剩余需要选 k - path.size() 个，从 i 到 n 要至少有这么多数
int need = k - path.size();
int upperBound = n - need + 1;
for (int i = start; i <= upperBound; i++) {
path.add(i);
backtrack(n, k, i + 1, path);
path.remove(path.size() - 1);
}
}
}Mermaid 图：剪枝效果（n=5, k=3）
复杂度分析
- 时间复杂度： O(C(n,k) × k)，剪枝后只访问"有效"节点，总节点数恰好等于 C(n,0) + C(n,1) + ... + C(n,k)（实际上就是 2^n 的一部分，更精确的分析见下）。
- 注意： 剪枝不改变最坏情况的渐进复杂度（因为有效子集数量本身就是 C(n,k)），但实际运行时间会有显著减少，因为减少了"进入必然失败分支"的开销。
四、解法三：迭代（利用字典序枚举）
思路
用一个长度为 k 的数组表示当前组合，按字典序枚举。初始化为 [1,2,...,k]，每次找到最右边可以递增的位置，递增后将其右边的所有位置重置为最小可能值。
import java.util.*;
public class Solution_Iterative {
public List<List<Integer>> combine(int n, int k) {
List<List<Integer>> result = new ArrayList<>();
// 初始组合：[1, 2, ..., k]
int[] indices = new int[k];
for (int i = 0; i < k; i++) indices[i] = i + 1;
while (true) {
// 记录当前组合
List<Integer> combo = new ArrayList<>();
for (int idx : indices) combo.add(idx);
result.add(combo);
// 找到最右边可以递增的位置
int pos = k - 1;
while (pos >= 0 && indices[pos] == pos + n - k + 1) {
pos--;
}
if (pos < 0) break; // 所有组合都枚举完了
// 递增 pos 位置的数
indices[pos]++;
// pos 之后的位置重置为最小值
for (int i = pos + 1; i < k; i++) {
indices[i] = indices[i - 1] + 1;
}
}
return result;
}
}复杂度分析
- 时间复杂度： O(C(n,k) × k)，每个组合需要 O(k) 时间生成和记录。
- 空间复杂度： O(k)，只用了 indices 数组，不需要递归栈。
五、举一反三
剪枝思维的推广
组合的剪枝条件 i <= n - (k - path.size()) + 1 本质上是"剩余资源不足时提前终止"。这种剪枝思想可以推广到：
- 组合总和（LeetCode 39）：如果剩余目标值 < 当前最小候选数，提前终止。
- N 皇后（LeetCode 51）：如果剩余行数 < 还需要放置的皇后数，提前终止（虽然N皇后本身保证n行n列，不需要这种剪枝）。
- 字母组合：类似的剩余位数检查。
组合 vs 子集 vs 排列
子集：从 n 个中选任意数量（0到n），不限制k，在每个节点记录结果
组合：从 n 个中恰好选 k 个，只在叶子节点（path.size()==k）记录
排列：从 n 个中选 n 个，有序，用 visited 标记三者的回溯框架高度相似，区别在于：
- 终止条件（path.size()==k 还是处理完所有元素）
- 记录时机（叶子节点还是每个节点）
- 候选范围（从 start 开始还是从 0 开始）
六、踩坑实录
坑一：剪枝上界计算错误
// 错误：少 +1
int upperBound = n - (k - path.size());
// 正确：需要 +1
int upperBound = n - (k - path.size()) + 1;n - need + 1 是因为：我们需要从 i 到 n 至少有 need 个数，即 n - i + 1 >= need，解不等式得 i <= n - need + 1。少了 +1，会漏掉一个合法的起始位置，导致结果不完整。
坑二：path.size() 在递归过程中是动态变化的
剪枝条件中的 path.size() 是当前状态下的路径长度，不是 k。每次递归调用时，need = k - path.size() 的值不同，因此 upperBound 也不同。不要把这个值缓存到外部变量然后复用。
坑三：result.add 时要复制
和全排列一样，result.add(new ArrayList<>(path)) 必须复制，不能直接引用 path。
坑四：迭代方式的终止条件
迭代方式中，indices[pos] == pos + n - k + 1 是第 pos 个位置的最大可能值（后面还有 k-1-pos 个位置需要递增排列）。这个上界计算要准确，否则会无限循环或提前终止。
七、总结
组合是回溯模板的经典应用，更重要的是它展示了剪枝优化的完整推导过程：
- 先分析"什么情况下当前分支注定失败"（剩余元素不够选满 k 个）。
- 把这个条件转化为 i 的上界约束
i <= n - (k - path.size()) + 1。 - 将上界限制直接加入 for 循环条件，自动剪枝。
这种"分析失败条件→转化为上界约束→加入循环条件"的三步法，是回溯剪枝的通用思路，适用于大多数组合类回溯题。
| 解法 | 时间复杂度 | 空间复杂度 | 特点 |
|---|---|---|---|
| 朴素回溯 | O(C(n,k)×k) | O(k) | 有冗余分支 |
| 剪枝回溯 | O(C(n,k)×k) | O(k) | 无冗余，推荐 |
| 迭代字典序 | O(C(n,k)×k) | O(k) | 无递归开销 |
补充深入讲解：组合数学与剪枝的极致优化
组合数 C(n,k) 的增长速度与算法下界
从 n 个元素中选 k 个的组合数是 C(n,k) = n! / (k! × (n-k)!)。当 k = n/2 时（选一半元素），C(n,k) 的增长速度接近 2^n / sqrt(n)，这是组合数的最大值。任何枚举所有组合的算法，时间复杂度不可能低于 O(C(n,k) × k)（因为输出量本身就有这么多），这是理论下界。
我们的回溯算法加上剪枝，实际上非常接近这个理论下界。剪枝确保了回溯树的非叶节点数量与叶节点数量成正比（每个非叶节点对应有效的中间状态），没有浪费在注定会失败的分支上。
剪枝的数学原理
最优剪枝条件是：在 backtrack(start, path) 中，如果剩余可选元素不足以填满路径（即 n - start + 1 < k - path.size()，剩余元素数小于还需要选的元素数），则直接剪枝。
这个条件等价于：for 循环的上界不是 n，而是 n - (k - path.size()) + 1。用一个例子理解：n=5，k=3，当前已选 1 个元素（path.size()=1），还需选 2 个。for 循环的候选范围是 start 到 5-(3-1)+1=4（不是 5）。如果从下标 5 开始选，后面只剩 0 个元素，无法再选够 1 个，这条分支注定无解，提前剪掉。
剪枝前，for 循环枚举 start 到 n 共 n-start+1 个候选；剪枝后，只枚举 start 到 n-(k-path.size())+1 共 n-(k-path.size())-start+2 个候选。当 k 接近 n 时（选择大多数元素），剪枝极为有效，能剪掉大部分无效分支；当 k 远小于 n 时（只选少量元素），剪枝效果相对有限。
组合的迭代生成算法
除了回溯，组合还可以用迭代方式生成。核心思路是维护一个"组合的字典序"，从最小字典序的组合开始，每次找到下一个字典序更大的组合：
对于当前组合 [a1, a2, ..., ak]（下标从大到小排列），找到最右边可以递增的下标 i（即 a[i] < n - k + i + 1），将 a[i] 加1，并将 a[i+1..k-1] 设为 a[i]+1, a[i]+2, ...（最小可能值）。这样就得到了下一个组合。
迭代方式的优势是空间复杂度更低（不需要递归栈），且可以在任意位置暂停和继续，适合"分批生成"的场景。在某些工程场景中，组合数量极大，不能一次全部生成到内存，就需要这种"流式生成"的迭代方式。
组合与帕斯卡三角形（杨辉三角）
C(n,k) 满足递推关系 C(n,k) = C(n-1,k-1) + C(n-1,k)：从 n 个元素中选 k 个，要么包含第 n 个元素（则从剩余 n-1 个中选 k-1 个），要么不包含（则从 n-1 个中选 k 个）。这正是帕斯卡三角形（杨辉三角）的构造规则。
回溯算法恰好体现了这个递推：backtrack(n, k) 先选一个元素（对应"包含某个元素"的分支），再递归调用 backtrack 处理剩余问题（对应更小规模的子问题）。两种分解方式（包含或不包含当前元素）对应帕斯卡三角形的两个方向。
这个联系不只是数学上的优美，在动态规划求组合数时也很实用：当只需要知道组合数的值（不需要枚举所有组合），可以直接用帕斯卡三角形的 DP 在 O(n×k) 时间内计算，比枚举更高效。
组合在工程中的应用
组合枚举在工程中最直接的应用是多种选择的穷举测试。例如，一个接口有 n 个可选参数，测试需要覆盖所有 k 个参数同时开启的场景——这就是从 n 个参数中选 k 个的组合枚举。
另一个常见应用是特征工程中的特征组合分析：当有 n 个特征时，枚举所有 2 个特征的组合（C(n,2) 个）、3 个特征的组合（C(n,3) 个）分析它们的交叉效果。n 不大时，这种穷举是可行的。
在密码学中，某些攻击算法（如差分攻击）需要枚举输入的所有可能组合来分析加密算法的特性，组合枚举是基础工具之一。
还有一个有趣的应用是数据库索引设计：当有 n 个字段时，选择哪 k 个字段建立复合索引，需要评估 C(n,k) 个候选索引的性能。自动化索引推荐工具需要高效枚举这些组合。
组合剪枝的实际效果量化
以 n=10，k=5 为例，分析剪枝前后的回溯树规模对比。
不带剪枝：for 循环从 start 到 n-1，共 n-start 个候选，递归深度 k=5。最坏情况下树的节点数约为 n^k = 10^5 = 100000。
带剪枝：for 循环从 start 到 n-(k-path.size())+1，有效缩减了每层的候选数量。实际树中，叶节点数 = C(10,5) = 252，非叶节点数约为 C(10,5) + C(10,4) + C(10,3) + C(10,2) + C(10,1) ≈ 252+210+120+45+10 = 637。总节点数约为 889，比不剪枝的 100000 缩减了 99% 以上。
对于 n 较大、k 接近 n/2 的情况，剪枝效果最为明显（因为无效分支最多）；对于 k 远小于 n 的情况（只选少量元素），剪枝效果有限（因为大多数分支本来就能到达叶子）。
理解了这个量化对比，就能在面试中有底气地说"加上剪枝后，时间复杂度从 O(n^k) 降低到 O(C(n,k) × k)，接近理论最优"，展示对算法效率的深入理解。
组合问题的一般化框架
组合问题（LeetCode 77）是回溯在组合数学上的标准应用，也是所有组合类回溯题的基础。后续的组合总和（LeetCode 39/40）、子集（LeetCode 78/90）都建立在组合回溯的框架上，区别只在于：
子集 = 枚举所有大小（k 从 0 到 n）的组合。组合总和 = 有求和约束的组合，且允许重复选取。组合总和 II = 有求和约束的组合，每个元素最多用一次，含重复元素需去重。
掌握了 LeetCode 77 的剪枝模板，配合不同的约束条件，就能灵活应对这一系列变形题。
组合问题的面试答题策略
在面试中遇到组合问题（LeetCode 77），有一个被很多面试官认可的解题思路展示顺序：
第一步，说出朴素回溯的思路（不带剪枝），展示对问题结构的基本理解；第二步，指出朴素解法的性能问题（大量无效分支），引出剪枝的必要性；第三步，展示剪枝条件的推导（剩余可选元素不足时提前终止），说明剪枝的正确性；第四步，给出带剪枝的完整代码，并分析优化后的时间复杂度（O(C(n,k)×k)，接近理论最优）。
这个展示顺序体现了"先理解问题，再识别瓶颈，再优化"的算法设计思维，比直接给出最优代码更有说服力。
组合与递归的学习心得
组合问题是"从 n 中选 k 个"，看似简单，但回溯框架的正确实现需要理解三个关键点：start 参数保证了元素按顺序选取（避免重复组合）；for 循环的上界剪枝保证了只有有效分支被探索；回溯（path.remove）保证了每条路径的状态被正确还原。
这三个关键点是所有组合类回溯题的共同基础。掌握了这三点，不只是会写 LeetCode 77，而是构建了可扩展的"组合回溯"思维框架，能灵活应对各种变形。
组合题的一句话核心思路
LeetCode 77 的核心思路一句话：用 start 参数保证元素按下标递增选取（避免重复组合），用剪枝条件 i <= n-(k-path.size()) 砍掉注定无解的分支（余下的元素数不够填满路径时提前终止）。这两句话包含了组合回溯的全部精华，能用自己的话解释清楚，就说明真正掌握了这道题。
组合回溯的两个关键设计决策：一是 start 参数（保证按顺序选取，避免重复组合）；二是剪枝（余下元素不足时提前终止）。两个决策各自独立，合在一起构成了高效的组合枚举。理解了这两点，就能在任何变形题中快速写出正确的组合回溯代码。
C(n,k) 的组合数公式与回溯剪枝的结合，是这道题最重要的知识点，也是面试中最有价值的谈资。
组合问题的剪枝是回溯效率提升的核心手段，理解剪枝条件的数学本质，是解决所有组合类问题的关键。