企业官网建设流程全解析

这题我原来是沿着“先选一个数，再处理后面的位置”想的。这个入口没问题，真正容易漏的细节是：递归回来，path要恢复成什么；答案要保存哪个对象；剩下数量不够时，循环应该在哪停。

1. 组合不区分顺序，所以我只生成递增路径

力扣77：组合，从1～n选出k个不同的数，返回所有组合，答案的外部顺序不限。原题范围为1≤n≤20、1≤k≤n。

例如n=4、k=2，[1,2]和[2,1]是同一组合。与其先生成全部排列再用集合去重，我直接规定下一次选择必须更大。

选1：下一层只能选2、3、4 选2：下一层只能选3、4 选3：下一层只能选4

因此dfs(i + 1)的含义是“下一层从i后面的数开始选”，不是“下一层选第i+1个位置”。start是候选数下界，path.size()才表示当前选了几个。

2. 原图的红字：选4以后没结果，也得恢复现场

原来的未剪枝代码，在第一层也会选择4，进入dfs(5)。这时path只有一个元素，还没凑够两个，但已经没有候选数；循环不执行，函数返回。外层仍要把刚加入的4移除。

这就是我原图想提醒的地方：递归没产出答案，不代表当前选择没有发生。回溯恢复的是进入下一层之前的现场，而不只是“成功找到答案后再清理”。

每次循环的状态应该对应：

进入循环：path = P 加入i： path = P + [i] 递归回来：path仍为 P + [i] 移除末尾：path恢复为 P

这里假设下一层自己恢复了它增加的元素。于是这一层只移除自己添加的i，兄弟分支不会带着前一个分支的内容继续走。

3. 原文说有剪枝，原代码其实没有

旧代码循环到i <= n，会走到剩余数量不足的分支，然后通过空循环自然返回。它能正确枚举，但这不等于已经实现了正文里的数量剪枝。

当前还缺need = k - path.size()个数。如果把i作为下一个数，那么从i到n一共只有n - i + 1个候选数。要有可能完成，必须：

n - i + 1 >= need i <= n - need + 1

这个候选上界包含本轮要选的i，所以有一个加1。n=4、k=2、path为空时，need=2，第一层只试1、2、3，原图中“选4后失败”的分支就不再进入。但第一层选3之后，下一层仍应允许选4，才能得到[3,4]。

4. 修订后的Java实现

保留原来的共享path、答案快照和添加/移除结构，只把剪枝明确落到循环边界，清理正文里与Java不一致的C++参数说明。

import java.util.ArrayList; import java.util.List; class Solution { private List<Integer> path; private List<List<Integer>> ret; private int n, k; public List<List<Integer>> combine(int n, int k) { this.n = n; this.k = k; path = new ArrayList<>(); ret = new ArrayList<>(); dfs(1); return ret; } private void dfs(int start) { if (path.size() == k) { ret.add(new ArrayList<>(path)); return; } int need = k - path.size(); for (int i = start; i <= n - need + 1; i++) { path.add(i); dfs(i + 1); path.remove(path.size() - 1); } } }

new ArrayList<>(path)保存的是当时的列表快照。如果改成ret.add(path)，ret里会存入同一个可变列表的多份引用；后面移除元素，已保存的“答案”也跟着变。Integer是不可变的，这里复制列表已足够，不必另做元素深拷贝。

每次combine重新建立path、ret，所以同一个实例顺序调用不会把上次答案混进这次。它使用实例字段，不是线程安全的并发工具；本题无需把它包装成并发接口。

5. 为什么不重、不漏，剪枝不删合法答案

所有路径严格递增，同一集合只有一种递增表示，因而不重。任意合法组合都可以按升序排列，它的每个下一项都在start之后，所以递归原本能走到它，因而不漏。

剪枝只排除剩下候选数连need个都凑不齐的选择，合法组合在每个前缀上都仍有足够候选数，不会被删。尤其要测试k=1、k=n、最后一个合法组合，这些位置最容易暴露上界少写加1的错误。

6. 验证：参考程序不再写一份相同的dfs

本次测试直接编译文章中的Solution。参考方法使用位掩码：对较小的n遍历所有子集，只留下恰好k位为1的掩码；第j位代表是否选择数字j+1。它没有沿用start和剪枝上界，避免把同一个边界错误复制进验证器。

以下是参考函数的核心，位移范围限定在本题的小n内，不把它当任意大n的写法：

static java.util.Set<String> reference(int n, int k) { java.util.Set<String> expected = new java.util.HashSet<>(); for (int mask = 0; mask < (1 << n); mask++) { if (Integer.bitCount(mask) != k) continue; java.util.List<Integer> one = new java.util.ArrayList<>(); for (int bit = 0; bit < n; bit++) { if ((mask & (1 << bit)) != 0) one.add(bit + 1); } expected.add(one.toString()); } return expected; }

这是放进测试类的方法，不是独立可编译的类。完整测试器还检查每行长度、元素范围、严格递增、答案重复和列表对象共享；只把结果转成Set比较会掩盖重复输出，因此先比较原始条数与去重后的条数。

本次Java17验证：n=1～12的全部78组合法n/k与位掩码参考结果一致；再测n=20的k=1、10、19、20，共82组。大组检查有效性、唯一性和二项式计数，k=10返回184756个合法且不同的组合。没有声称枚举了所有n≤20的输入。

PASS: 82 combination cases + repeat-call/snapshot checks

同一实例重复调用、保存旧结果后再调用也单独检查。另把剪枝上界漏掉加1、答案存共享path、回退不移除三种错误版本交给验证器，均被拒绝。测试脚本及运行证据保留在本地工作台，不是截图后只说“应该没问题”。

7. 剪枝不能消除输出答案的成本

结果本身有C(n,k)行，每行k个数字，保存答案就至少需要与k*C(n,k)成正比的时间和空间。该剪枝实现的时间可用 O(k*C(n,k)) 作为上界；不含输出结果的递归栈和path为O(k)。不能只看递归深度，就把枚举全部答案说成O(k)时间。

原图保留的是未剪枝过程，本次程序跳过数量不足的分支，两者不该被当作完全相同的执行轨迹。真正贯穿它们的思路没变：用start避免排列重复，用快照保存答案，用回退恢复当前选择，再用数量不够这个事实做剪枝。