最初我整理了回溯的模板做选择、递归、撤销选择。这个顺序是核心但只看模板还回答不了标题里的问题这些词到底在比较什么它们并不是五个只能选一个的算法。同一个程序完全可以穷举组合用DFS访问状态靠回溯恢复路径再通过剪枝省掉不可能成功的分支。1. 先让每个词回答不同的问题词本文中的含义回答的问题穷举系统检查候选情况哪些候选需要考虑暴搜通常指优化较少、直接搜索的解法是否直接展开大量状态DFS/深搜深度优先访问状态下一步先深入哪条分支回溯试探后恢复状态继续其他选择怎样共享并恢复当前路径剪枝根据条件排除不可能产生所需答案的分支哪些分支可以提前停止“暴搜”不是严格统一的复杂度类别DFS也不等于“必然指数时间”。在图中每个顶点只访问一次的DFS与这里的组合状态树是不同规模的问题。2. 用一道题把它们放到一起从1..n中选出k个不同数字不考虑顺序输出所有组合。例如n4,k3[1,2,3] [1,2,4] [1,3,4] [2,3,4]对每个数字只决定选或不选。没有剪枝时走到第n个数字之后才能知道这一条路径是不是刚好选了k个。这个模型会检查所有子集属于穷举递归先走“选”再走“不选”是DFS访问顺序当前路径在递归之间复用则需要回溯。下面只画一小段不是假装把完整搜索树都画完path[1,2]接下来处理3 | -- 选3 -- [1,2,3] -- 后续不选4 -- 保存[1,2,3] | -- 撤销3恢复[1,2] | -- 不选3 -- 选4 -- 保存[1,2,4]撤销不是“本次选择错误了才做”。即使刚刚找到一个正确答案也要恢复路径才能继续找下一个。3. 剪枝来自一个能证明的条件当前已经选了have个尚有remaining个数字没处理。如果have k已经选多了如果have remaining k即使全选也不够。这两种状态都不可能产生合法组合可以停止。n4,k3已经跳过1和2 当前path[]只剩3和4 即使全部选中也只有2个 3个 因此整个后续分支都不必展开条件里必须是严格小于。刚好还有足够数字时仍可能成功例如已经选了[1,2]只剩4目标是3个213恰好应该保留。剪枝的任务是省搜索不是改答案。枚举所有解时不能随意套用“已经找到一个更好的值就停止”的规则。4. 可以运行的完整C程序保存为SearchProbe.cpp编译运行g -stdc17 -O2 -Wall -Wextra -pedantic SearchProbe.cpp -o SearchProbe ./SearchProbe这里使用C与原文vector模板一致不将它当作C代码。程序比较的是同一棵选/不选树加剪枝前后的区别。#include algorithm #include iostream #include stdexcept #include vector using Answers std::vectorstd::vectorint; struct Search { int n, k; bool prune; long long visits 0; std::vectorint path; Answers answers; void dfs(int next) { visits; int have static_castint(path.size()); int remaining n - next 1; if (prune (have k || have remaining k)) return; if (next n 1) { if (have k) answers.push_back(path); return; } path.push_back(next); dfs(next 1); path.pop_back(); dfs(next 1); } }; Answers oracle(int n, int k) { Answers result; for (unsigned mask 0; mask (1u n); mask) { std::vectorint chosen; for (int bit 0; bit n; bit) if (mask (1u bit)) chosen.push_back(bit 1); if (static_castint(chosen.size()) k) result.push_back(chosen); } std::sort(result.begin(), result.end()); return result; } int main() { Search plain{4, 3, false, 0, {}, {}}; Search pruned{4, 3, true, 0, {}, {}}; plain.dfs(1); pruned.dfs(1); for (const auto answer : pruned.answers) { for (int x : answer) std::cout x ; std::cout \n; } std::cout visits: plain.visits - pruned.visits \n; int cases 0; for (int n 0; n 12; n) { for (int k 0; k n 1; k) { auto expected oracle(n, k); for (bool prune : {false, true}) { Search test{n, k, prune, 0, {}, {}}; test.dfs(1); std::sort(test.answers.begin(), test.answers.end()); if (test.answers ! expected || !test.path.empty()) throw std::runtime_error(answer or restoration mismatch); } cases; } } std::cout PASS: cases input pairs; both versions match bitmask oracle\n; }visits统计函数入口次数包括进入后立即被剪掉的状态。它不是运行时间也不代表所有DFS都能减少相同比例的工作。本地编译执行得到1 2 3 1 2 4 1 3 4 2 3 4 visits: 31 - 21 PASS: 104 input pairs; both versions match bitmask oracle比较范围是n0..12、每个n的k0..n1共104组输入两种递归版本都与位掩码结果一致。这里只省掉不可能满足数量的分支还可以有其他优化数字不是剪枝能力的通用上限。5. 为什么验证不只数答案假设应该有4个答案错误程序重复输出了4次同一组数字只查数量仍会通过。因此程序拿另一种表示法做对照位掩码直接枚举子集再与递归输出的完整集合排序比较。同时检查递归结束后path回到空状态验证撤销动作没有漏掉。测试范围含n0,k0、k0、kn、kn1不仅是题目样例。位掩码测试限制n不超过12避免移位越界和指数规模失控这是教学验证器不是任意规模输入的评测服务。验证时另生成了一份错误版本将“不够选”的严格小于改成小于等于它错误地删掉刚好够选的状态被集合对照检出。这份错误版本不是上面正文的正常程序。6. 空间低不低要说清比较对象这里不会保存整棵状态树只保存当前路径和递归栈。排除输出集合后辅助空间为O(n)保存全部组合还需要对应的结果空间。不剪枝的二叉树有2^(n1)-1次函数访问复制输出还要计入组合内容。不能因为“只维护一条路径”就一概写成空间复杂度低也不能把输出开销藏起来。组合里[1,2]和[2,1]是同一个结果排列里它们不同。子集同样不考虑元素顺序。这也是原模板不能不加修改就解决所有问题的原因题目决定合法状态、候选选择和去重方式。最后回看五个词穷举讲候选覆盖DFS讲访问顺序回溯讲状态恢复剪枝讲提前排除。“暴搜”通常描述直接搜索的做法它们可以同时出现在一个程序里。