组合题回溯：start如何去重，path如何恢复，剪枝上界怎么推

这题我原来是沿着“先选一个数再处理后面的位置”想的。这个入口没问题真正容易漏的细节是递归回来path要恢复成什么答案要保存哪个对象剩下数量不够时循环应该在哪停。1. 组合不区分顺序所以我只生成递增路径力扣77组合从1n选出k个不同的数返回所有组合答案的外部顺序不限。原题范围为1≤n≤20、1≤k≤n。例如n4、k2[1,2]和[2,1]是同一组合。与其先生成全部排列再用集合去重我直接规定下一次选择必须更大。选1下一层只能选2、3、4 选2下一层只能选3、4 选3下一层只能选4因此dfs(i 1)的含义是“下一层从i后面的数开始选”不是“下一层选第i1个位置”。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。n4、k2、path为空时need2第一层只试1、2、3原图中“选4后失败”的分支就不再进入。但第一层选3之后下一层仍应允许选4才能得到[3,4]。4. 修订后的Java实现保留原来的共享path、答案快照和添加/移除结构只把剪枝明确落到循环边界清理正文里与Java不一致的C参数说明。import java.util.ArrayList; import java.util.List; class Solution { private ListInteger path; private ListListInteger ret; private int n, k; public ListListInteger 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个都凑不齐的选择合法组合在每个前缀上都仍有足够候选数不会被删。尤其要测试k1、kn、最后一个合法组合这些位置最容易暴露上界少写加1的错误。6. 验证参考程序不再写一份相同的dfs本次测试直接编译文章中的Solution。参考方法使用位掩码对较小的n遍历所有子集只留下恰好k位为1的掩码第j位代表是否选择数字j1。它没有沿用start和剪枝上界避免把同一个边界错误复制进验证器。以下是参考函数的核心位移范围限定在本题的小n内不把它当任意大n的写法static java.util.SetString reference(int n, int k) { java.util.SetString expected new java.util.HashSet(); for (int mask 0; mask (1 n); mask) { if (Integer.bitCount(mask) ! k) continue; java.util.ListInteger 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验证n112的全部78组合法n/k与位掩码参考结果一致再测n20的k1、10、19、20共82组。大组检查有效性、唯一性和二项式计数k10返回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避免排列重复用快照保存答案用回退恢复当前选择再用数量不够这个事实做剪枝。