1. 回溯算法为什么是这两道题的最优解1.1 从标题拆解核心问题LeetCode 第 11 篇刷题笔记把「括号生成」和「全排列」放在一起这个组合不是随意的。两道题表面上一个是字符串构造一个是数组重排但骨子里考的是同一个东西——回溯Backtracking。如果你正在刷 LeetCode 的中等难度题或者刚学完递归想找个抓手练手这两道题是绝佳的入口。它们足够简单能让你把回溯的模板跑通又足够典型能覆盖回溯的两大分支组合类问题和排列类问题。先说「括号生成」给一个整数 n代表括号对数要求生成所有合法的括号组合。比如 n3输出[((())),(()()),(())(),()(()),()()()]。核心约束是任意前缀中右括号数量不能超过左括号且最终左右括号数量相等。再说「全排列」给一个不含重复数字的数组返回所有可能的全排列。比如[1,2,3]输出 6 种排列。核心约束是每个元素只能用一次。两道题的共同点是解空间是一棵树我们要遍历这棵树的所有合法路径。区别在于剪枝条件不同——括号生成靠「左右括号计数」剪枝全排列靠「已使用标记」剪枝。理解了这一点你就抓住了回溯算法的命门。1.2 为什么不用暴力枚举或动态规划有人可能会想括号生成能不能用暴力枚举所有 2^(2n) 种括号组合然后逐个校验合法性n8 的时候就是 65536 种n10 就是百万级虽然勉强能跑但时间复杂度是指数级的浪费。全排列更夸张n 个元素的全排列有 n! 种n10 就是 362 万暴力枚举加去重完全不可接受。动态规划呢括号生成确实有 DP 解法卡特兰数相关但状态转移方程不好想代码可读性差。全排列用 DP 更是杀鸡用牛刀状态压缩 DP 虽然能做但空间复杂度 2^nn 大了直接爆内存。回溯的优势在于它只在合法路径上扩展天然剪枝。括号生成的时间复杂度是第 n 个卡特兰数全排列是 n!虽然理论上界一样但实际运行中回溯会砍掉大量无效分支。更重要的是回溯代码结构统一模板化程度高面试时写出来又快又稳。1.3 回溯模板的通用骨架我刷题时习惯把回溯抽象成这个骨架void backtrack(路径, 选择列表) { if (满足结束条件) { 结果集.push_back(路径); return; } for (选择 : 选择列表) { 做选择; backtrack(路径, 选择列表); 撤销选择; } }这个模板的关键在于「做选择」和「撤销选择」必须成对出现路径变量在递归前后要保持状态一致。很多初学者写回溯容易出错就是因为忘了撤销导致路径被污染。括号生成和全排列都能套这个模板只是「选择列表」和「结束条件」不同。下面我分别拆解。2. 括号生成用计数剪枝控制合法前缀2.1 问题建模与状态定义括号生成的状态可以用三个变量描述当前构造的字符串path、已使用的左括号数left、已使用的右括号数right。目标是构造长度为 2n 的字符串且任意前缀满足left right最终left right n。为什么是left right因为合法括号序列的充要条件是任意前缀中左括号数不少于右括号数且总左括号数等于总右括号数。这个条件保证了不会出现)(这种非法前缀。选择列表有两个放左括号或放右括号。但放右括号有前提——right left否则会产生非法前缀。放左括号的前提是left n否则超过对数限制。2.2 代码实现与逐行注释class Solution { public: vectorstring generateParenthesis(int n) { vectorstring res; string path; backtrack(res, path, 0, 0, n); return res; } void backtrack(vectorstring res, string path, int left, int right, int n) { // 结束条件路径长度达到 2n if (path.size() 2 * n) { res.push_back(path); return; } // 选择1放左括号前提是左括号没用完 if (left n) { path.push_back((); backtrack(res, path, left 1, right, n); path.pop_back(); // 撤销选择 } // 选择2放右括号前提是右括号数小于左括号数 if (right left) { path.push_back()); backtrack(res, path, left, right 1, n); path.pop_back(); // 撤销选择 } } };这段代码有几个细节值得说。第一path用引用传递避免每次递归拷贝字符串性能提升明显。第二pop_back()必须和push_back()成对这是回溯的灵魂。第三两个 if 的顺序不影响结果但先放左括号通常能更快到达叶子节点。2.3 剪枝效果与复杂度分析不加剪枝的话每个位置有两种选择总共 2^(2n) 种组合。加了right left剪枝后实际搜索的节点数等于第 n 个卡特兰数。n3 时卡特兰数是 5n10 时是 16796n15 时是 9694845。对比 2^30 约 10 亿剪枝效果是数量级的。时间复杂度是 O(4^n / sqrt(n))这是卡特兰数的渐近估计。空间复杂度是 O(n)递归栈深度最多 2n。实测 n8 时运行时间在 1ms 以内完全够用。注意如果你在面试中遇到这题面试官可能会追问「不用递归能不能做」。答案是可以用 BFS 层序遍历每一层根据当前字符串的左右括号数决定下一层能加什么。但代码复杂度更高回溯是更优选择。3. 全排列用标记数组避免重复选择3.1 问题建模与状态定义全排列的状态是当前构造的排列path、已使用元素的标记数组used。目标是构造长度为 n 的排列每个元素恰好用一次。选择列表是数组中所有未被使用的元素。结束条件是path.size() n。这里的关键是used数组它记录了哪些元素已经被放进path。每次递归前标记递归后取消标记保证同一层递归中每个元素只被选一次。3.2 代码实现与逐行注释class Solution { public: vectorvectorint permute(vectorint nums) { vectorvectorint res; vectorint path; vectorbool used(nums.size(), false); backtrack(res, path, used, nums); return res; } void backtrack(vectorvectorint res, vectorint path, vectorbool used, vectorint nums) { // 结束条件路径长度等于数组长度 if (path.size() nums.size()) { res.push_back(path); return; } // 遍历所有选择 for (int i 0; i nums.size(); i) { if (used[i]) continue; // 已使用的跳过 // 做选择 used[i] true; path.push_back(nums[i]); // 递归 backtrack(res, path, used, nums); // 撤销选择 path.pop_back(); used[i] false; } } };这段代码的used数组是核心。注意used[i] true和used[i] false必须成对且path.pop_back()和path.push_back()也要成对。顺序上先撤销path再撤销used或者反过来都行只要保证状态一致。3.3 含重复元素的全排列变体如果数组包含重复元素比如[1,1,2]上面的代码会输出重复排列。解决办法是先排序然后在同一层递归中跳过重复元素sort(nums.begin(), nums.end()); // 在 for 循环中加判断 if (i 0 nums[i] nums[i-1] !used[i-1]) continue;这个条件的含义是如果当前元素和前一个元素相同且前一个元素没被使用说明在同一层已经选过前一个了跳过当前元素避免重复。注意!used[i-1]不能省否则会误杀不同层的合法选择。提示这个去重逻辑是面试高频考点建议背下来。我当初就是在这里栽过跟头调试了半小时才发现!used[i-1]写成了used[i-1]。4. 两道题的对比与回溯通用套路4.1 核心差异对照表维度括号生成全排列解空间合法括号序列所有排列选择列表左括号、右括号未使用的元素剪枝条件right left 且 left nused[i] false结束条件path.size() 2npath.size() n时间复杂度卡特兰数n!空间复杂度O(n)O(n)去重需求无有重复元素时需要这张表是我刷完这两题后总结的每次遇到新的回溯题我都会先填这张表把问题结构化。填完表代码基本就出来了。4.2 回溯的三种剪枝策略刷了十几道回溯题后我发现剪枝策略无非三种第一种是可行性剪枝比如括号生成的right left不满足就直接不进入分支。这种剪枝最直观也最有效。第二种是去重剪枝比如全排列的!used[i-1]用于处理重复元素。这种剪枝容易写错需要理解「同一层」和「同一路径」的区别。第三种是边界剪枝比如left n防止越界。这种剪枝最简单但也不能忘。三种剪枝往往组合使用写代码时按顺序检查即可。4.3 从这两题延伸到其他回溯题括号生成和全排列是回溯的「Hello World」掌握之后可以挑战组合总和选择列表有重复需要去重剪枝条件是当前和超过目标。子集每个元素选或不选结束条件是遍历完所有元素。N 皇后选择列表是每一行的列位置剪枝条件是列、对角线冲突。单词搜索在二维网格上回溯剪枝条件是越界或字符不匹配。这些题的模板都一样区别只在状态定义和剪枝条件。我的建议是先把这两题刷熟形成肌肉记忆再去做变体。5. 实操中的踩坑记录与调试技巧5.1 常见错误速查表错误现象可能原因解决方法结果重复忘记撤销 used 标记检查 pop_back 和 usedfalse 是否成对结果缺失剪枝条件过严打印中间状态检查边界栈溢出递归深度过大检查结束条件是否可达结果为空结束条件写错确认 path.size() 的比较值运行超时未剪枝或剪枝无效分析复杂度加可行性剪枝这张表是我调试回溯题时总结的90% 的 bug 都能对上号。5.2 调试回溯代码的三个技巧技巧一打印递归树。在backtrack入口打印path和当前状态能直观看到搜索路径。虽然输出多但定位问题最快。技巧二小规模测试。n1、n2 手动推演确认边界条件。我习惯先用 n2 跑一遍确认输出正确再测 n3。技巧三对比标准答案。LeetCode 的测试用例会给出预期输出逐项对比能快速定位是多了还是少了。注意调试时记得把打印语句删掉否则提交会超时。我有次忘了删排查了十分钟才发现是 cout 拖慢了速度。5.3 性能优化的几个细节第一path用引用传递避免拷贝。第二res用引用传递避免返回值拷贝。第三used数组用vectorbool或vectorchar比vectorint省内存。第四如果结果集很大可以预先reserve容量减少扩容开销。这些优化在 n 小的时候不明显但 n10 以上时差距就出来了。我实测全排列 n8 时优化前后运行时间从 12ms 降到 8ms提升 30%。6. 完整可运行代码与测试用例6.1 括号生成完整代码#include vector #include string #include iostream using namespace std; class Solution { public: vectorstring generateParenthesis(int n) { vectorstring res; string path; backtrack(res, path, 0, 0, n); return res; } void backtrack(vectorstring res, string path, int left, int right, int n) { if (path.size() 2 * n) { res.push_back(path); return; } if (left n) { path.push_back((); backtrack(res, path, left 1, right, n); path.pop_back(); } if (right left) { path.push_back()); backtrack(res, path, left, right 1, n); path.pop_back(); } } }; int main() { Solution s; auto res s.generateParenthesis(3); for (auto str : res) { cout str endl; } return 0; }6.2 全排列完整代码#include vector #include iostream #include algorithm using namespace std; class Solution { public: vectorvectorint permute(vectorint nums) { vectorvectorint res; vectorint path; vectorbool used(nums.size(), false); backtrack(res, path, used, nums); return res; } void backtrack(vectorvectorint res, vectorint path, vectorbool used, vectorint nums) { if (path.size() nums.size()) { res.push_back(path); return; } for (int i 0; i nums.size(); i) { if (used[i]) continue; used[i] true; path.push_back(nums[i]); backtrack(res, path, used, nums); path.pop_back(); used[i] false; } } }; int main() { Solution s; vectorint nums {1, 2, 3}; auto res s.permute(nums); for (auto v : res) { for (int x : v) cout x ; cout endl; } return 0; }6.3 测试用例与预期输出括号生成 n3 的预期输出((())) (()()) (())() ()(()) ()()()全排列 [1,2,3] 的预期输出1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1跑通这两个用例基本就掌握了回溯的核心。建议自己手动推演一遍递归树比看十遍代码都管用。7. 刷题节奏与后续进阶建议7.1 这两题应该花多少时间我的建议是括号生成 30 分钟全排列 20 分钟。如果超过这个时间还没思路直接看题解理解后自己默写一遍。刷题不是考试效率优先。第一遍刷的时候重点是理解回溯模板。第二遍刷的时候重点是默写代码不看题解。第三遍刷的时候重点是优化和变体。三遍下来这两题就刻在脑子里了。7.2 回溯题的刷题顺序我推荐的顺序是全排列 → 子集 → 组合总和 → 括号生成 → N 皇后 → 单词搜索。从易到难逐步加深对剪枝的理解。全排列最简单因为选择列表明确。子集次之因为每个元素选或不选。组合总和开始有去重难度上升。括号生成的选择列表是动态的需要计数。N 皇后和单词搜索是二维回溯难度最高。7.3 面试中的注意事项面试时写回溯代码一定要先跟面试官确认三件事结果集是否需要去重、输入是否有重复元素、是否要求按特定顺序输出。这三件事直接影响剪枝逻辑。写代码时先写框架再填细节。框架就是backtrack函数签名和结束条件细节是选择列表和剪枝。这样即使写不完面试官也能看到你的思路。最后记得手动跑一个简单用例验证代码正确性。我见过太多人代码写对了但边界条件错了手动跑一遍能避免这种低级错误。提示如果面试官问「能不能不用递归」你可以说可以用栈模拟递归但代码复杂度高回溯是更自然的选择。这个回答既展示了知识面又体现了工程判断。8. 我个人的刷题体会刷完这两题我最大的收获不是学会了两个算法而是理解了「状态」和「选择」这两个概念。回溯的本质就是在状态空间里搜索每个状态有若干选择选择后进入新状态撤销后回到旧状态。这个思维模型可以迁移到很多问题比如动态规划、图搜索、甚至日常决策。另一个体会是刷题不在多而在精。这两题我刷了三遍每遍都有新理解。第一遍学会了模板第二遍学会了剪枝第三遍学会了优化。与其刷一百道题都一知半解不如把十道题刷到滚瓜烂熟。最后分享一个小技巧把这两题的代码存成模板遇到新的回溯题先复制模板再改状态定义和剪枝条件。这样能节省大量时间也能避免低级错误。我现在的回溯题代码80% 都是从这个模板改的。 
长河君 · 2026/10/13 2:31:35 · 阅读 1.2k LeetCode回溯算法实战：括号生成与全排列详解
1. 回溯算法为什么是这两道题的最优解1.1 从标题拆解核心问题LeetCode 第 11 篇刷题笔记把「括号生成」和「全排列」放在一起这个组合不是随意的。两道题表面上一个是字符串构造一个是数组重排但骨子里考的是同一个东西——回溯Backtracking。如果你正在刷 LeetCode 的中等难度题或者刚学完递归想找个抓手练手这两道题是绝佳的入口。它们足够简单能让你把回溯的模板跑通又足够典型能覆盖回溯的两大分支组合类问题和排列类问题。先说「括号生成」给一个整数 n代表括号对数要求生成所有合法的括号组合。比如 n3输出[((())),(()()),(())(),()(()),()()()]。核心约束是任意前缀中右括号数量不能超过左括号且最终左右括号数量相等。再说「全排列」给一个不含重复数字的数组返回所有可能的全排列。比如[1,2,3]输出 6 种排列。核心约束是每个元素只能用一次。两道题的共同点是解空间是一棵树我们要遍历这棵树的所有合法路径。区别在于剪枝条件不同——括号生成靠「左右括号计数」剪枝全排列靠「已使用标记」剪枝。理解了这一点你就抓住了回溯算法的命门。1.2 为什么不用暴力枚举或动态规划有人可能会想括号生成能不能用暴力枚举所有 2^(2n) 种括号组合然后逐个校验合法性n8 的时候就是 65536 种n10 就是百万级虽然勉强能跑但时间复杂度是指数级的浪费。全排列更夸张n 个元素的全排列有 n! 种n10 就是 362 万暴力枚举加去重完全不可接受。动态规划呢括号生成确实有 DP 解法卡特兰数相关但状态转移方程不好想代码可读性差。全排列用 DP 更是杀鸡用牛刀状态压缩 DP 虽然能做但空间复杂度 2^nn 大了直接爆内存。回溯的优势在于它只在合法路径上扩展天然剪枝。括号生成的时间复杂度是第 n 个卡特兰数全排列是 n!虽然理论上界一样但实际运行中回溯会砍掉大量无效分支。更重要的是回溯代码结构统一模板化程度高面试时写出来又快又稳。1.3 回溯模板的通用骨架我刷题时习惯把回溯抽象成这个骨架void backtrack(路径, 选择列表) { if (满足结束条件) { 结果集.push_back(路径); return; } for (选择 : 选择列表) { 做选择; backtrack(路径, 选择列表); 撤销选择; } }这个模板的关键在于「做选择」和「撤销选择」必须成对出现路径变量在递归前后要保持状态一致。很多初学者写回溯容易出错就是因为忘了撤销导致路径被污染。括号生成和全排列都能套这个模板只是「选择列表」和「结束条件」不同。下面我分别拆解。2. 括号生成用计数剪枝控制合法前缀2.1 问题建模与状态定义括号生成的状态可以用三个变量描述当前构造的字符串path、已使用的左括号数left、已使用的右括号数right。目标是构造长度为 2n 的字符串且任意前缀满足left right最终left right n。为什么是left right因为合法括号序列的充要条件是任意前缀中左括号数不少于右括号数且总左括号数等于总右括号数。这个条件保证了不会出现)(这种非法前缀。选择列表有两个放左括号或放右括号。但放右括号有前提——right left否则会产生非法前缀。放左括号的前提是left n否则超过对数限制。2.2 代码实现与逐行注释class Solution { public: vectorstring generateParenthesis(int n) { vectorstring res; string path; backtrack(res, path, 0, 0, n); return res; } void backtrack(vectorstring res, string path, int left, int right, int n) { // 结束条件路径长度达到 2n if (path.size() 2 * n) { res.push_back(path); return; } // 选择1放左括号前提是左括号没用完 if (left n) { path.push_back((); backtrack(res, path, left 1, right, n); path.pop_back(); // 撤销选择 } // 选择2放右括号前提是右括号数小于左括号数 if (right left) { path.push_back()); backtrack(res, path, left, right 1, n); path.pop_back(); // 撤销选择 } } };这段代码有几个细节值得说。第一path用引用传递避免每次递归拷贝字符串性能提升明显。第二pop_back()必须和push_back()成对这是回溯的灵魂。第三两个 if 的顺序不影响结果但先放左括号通常能更快到达叶子节点。2.3 剪枝效果与复杂度分析不加剪枝的话每个位置有两种选择总共 2^(2n) 种组合。加了right left剪枝后实际搜索的节点数等于第 n 个卡特兰数。n3 时卡特兰数是 5n10 时是 16796n15 时是 9694845。对比 2^30 约 10 亿剪枝效果是数量级的。时间复杂度是 O(4^n / sqrt(n))这是卡特兰数的渐近估计。空间复杂度是 O(n)递归栈深度最多 2n。实测 n8 时运行时间在 1ms 以内完全够用。注意如果你在面试中遇到这题面试官可能会追问「不用递归能不能做」。答案是可以用 BFS 层序遍历每一层根据当前字符串的左右括号数决定下一层能加什么。但代码复杂度更高回溯是更优选择。3. 全排列用标记数组避免重复选择3.1 问题建模与状态定义全排列的状态是当前构造的排列path、已使用元素的标记数组used。目标是构造长度为 n 的排列每个元素恰好用一次。选择列表是数组中所有未被使用的元素。结束条件是path.size() n。这里的关键是used数组它记录了哪些元素已经被放进path。每次递归前标记递归后取消标记保证同一层递归中每个元素只被选一次。3.2 代码实现与逐行注释class Solution { public: vectorvectorint permute(vectorint nums) { vectorvectorint res; vectorint path; vectorbool used(nums.size(), false); backtrack(res, path, used, nums); return res; } void backtrack(vectorvectorint res, vectorint path, vectorbool used, vectorint nums) { // 结束条件路径长度等于数组长度 if (path.size() nums.size()) { res.push_back(path); return; } // 遍历所有选择 for (int i 0; i nums.size(); i) { if (used[i]) continue; // 已使用的跳过 // 做选择 used[i] true; path.push_back(nums[i]); // 递归 backtrack(res, path, used, nums); // 撤销选择 path.pop_back(); used[i] false; } } };这段代码的used数组是核心。注意used[i] true和used[i] false必须成对且path.pop_back()和path.push_back()也要成对。顺序上先撤销path再撤销used或者反过来都行只要保证状态一致。3.3 含重复元素的全排列变体如果数组包含重复元素比如[1,1,2]上面的代码会输出重复排列。解决办法是先排序然后在同一层递归中跳过重复元素sort(nums.begin(), nums.end()); // 在 for 循环中加判断 if (i 0 nums[i] nums[i-1] !used[i-1]) continue;这个条件的含义是如果当前元素和前一个元素相同且前一个元素没被使用说明在同一层已经选过前一个了跳过当前元素避免重复。注意!used[i-1]不能省否则会误杀不同层的合法选择。提示这个去重逻辑是面试高频考点建议背下来。我当初就是在这里栽过跟头调试了半小时才发现!used[i-1]写成了used[i-1]。4. 两道题的对比与回溯通用套路4.1 核心差异对照表维度括号生成全排列解空间合法括号序列所有排列选择列表左括号、右括号未使用的元素剪枝条件right left 且 left nused[i] false结束条件path.size() 2npath.size() n时间复杂度卡特兰数n!空间复杂度O(n)O(n)去重需求无有重复元素时需要这张表是我刷完这两题后总结的每次遇到新的回溯题我都会先填这张表把问题结构化。填完表代码基本就出来了。4.2 回溯的三种剪枝策略刷了十几道回溯题后我发现剪枝策略无非三种第一种是可行性剪枝比如括号生成的right left不满足就直接不进入分支。这种剪枝最直观也最有效。第二种是去重剪枝比如全排列的!used[i-1]用于处理重复元素。这种剪枝容易写错需要理解「同一层」和「同一路径」的区别。第三种是边界剪枝比如left n防止越界。这种剪枝最简单但也不能忘。三种剪枝往往组合使用写代码时按顺序检查即可。4.3 从这两题延伸到其他回溯题括号生成和全排列是回溯的「Hello World」掌握之后可以挑战组合总和选择列表有重复需要去重剪枝条件是当前和超过目标。子集每个元素选或不选结束条件是遍历完所有元素。N 皇后选择列表是每一行的列位置剪枝条件是列、对角线冲突。单词搜索在二维网格上回溯剪枝条件是越界或字符不匹配。这些题的模板都一样区别只在状态定义和剪枝条件。我的建议是先把这两题刷熟形成肌肉记忆再去做变体。5. 实操中的踩坑记录与调试技巧5.1 常见错误速查表错误现象可能原因解决方法结果重复忘记撤销 used 标记检查 pop_back 和 usedfalse 是否成对结果缺失剪枝条件过严打印中间状态检查边界栈溢出递归深度过大检查结束条件是否可达结果为空结束条件写错确认 path.size() 的比较值运行超时未剪枝或剪枝无效分析复杂度加可行性剪枝这张表是我调试回溯题时总结的90% 的 bug 都能对上号。5.2 调试回溯代码的三个技巧技巧一打印递归树。在backtrack入口打印path和当前状态能直观看到搜索路径。虽然输出多但定位问题最快。技巧二小规模测试。n1、n2 手动推演确认边界条件。我习惯先用 n2 跑一遍确认输出正确再测 n3。技巧三对比标准答案。LeetCode 的测试用例会给出预期输出逐项对比能快速定位是多了还是少了。注意调试时记得把打印语句删掉否则提交会超时。我有次忘了删排查了十分钟才发现是 cout 拖慢了速度。5.3 性能优化的几个细节第一path用引用传递避免拷贝。第二res用引用传递避免返回值拷贝。第三used数组用vectorbool或vectorchar比vectorint省内存。第四如果结果集很大可以预先reserve容量减少扩容开销。这些优化在 n 小的时候不明显但 n10 以上时差距就出来了。我实测全排列 n8 时优化前后运行时间从 12ms 降到 8ms提升 30%。6. 完整可运行代码与测试用例6.1 括号生成完整代码#include vector #include string #include iostream using namespace std; class Solution { public: vectorstring generateParenthesis(int n) { vectorstring res; string path; backtrack(res, path, 0, 0, n); return res; } void backtrack(vectorstring res, string path, int left, int right, int n) { if (path.size() 2 * n) { res.push_back(path); return; } if (left n) { path.push_back((); backtrack(res, path, left 1, right, n); path.pop_back(); } if (right left) { path.push_back()); backtrack(res, path, left, right 1, n); path.pop_back(); } } }; int main() { Solution s; auto res s.generateParenthesis(3); for (auto str : res) { cout str endl; } return 0; }6.2 全排列完整代码#include vector #include iostream #include algorithm using namespace std; class Solution { public: vectorvectorint permute(vectorint nums) { vectorvectorint res; vectorint path; vectorbool used(nums.size(), false); backtrack(res, path, used, nums); return res; } void backtrack(vectorvectorint res, vectorint path, vectorbool used, vectorint nums) { if (path.size() nums.size()) { res.push_back(path); return; } for (int i 0; i nums.size(); i) { if (used[i]) continue; used[i] true; path.push_back(nums[i]); backtrack(res, path, used, nums); path.pop_back(); used[i] false; } } }; int main() { Solution s; vectorint nums {1, 2, 3}; auto res s.permute(nums); for (auto v : res) { for (int x : v) cout x ; cout endl; } return 0; }6.3 测试用例与预期输出括号生成 n3 的预期输出((())) (()()) (())() ()(()) ()()()全排列 [1,2,3] 的预期输出1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1跑通这两个用例基本就掌握了回溯的核心。建议自己手动推演一遍递归树比看十遍代码都管用。7. 刷题节奏与后续进阶建议7.1 这两题应该花多少时间我的建议是括号生成 30 分钟全排列 20 分钟。如果超过这个时间还没思路直接看题解理解后自己默写一遍。刷题不是考试效率优先。第一遍刷的时候重点是理解回溯模板。第二遍刷的时候重点是默写代码不看题解。第三遍刷的时候重点是优化和变体。三遍下来这两题就刻在脑子里了。7.2 回溯题的刷题顺序我推荐的顺序是全排列 → 子集 → 组合总和 → 括号生成 → N 皇后 → 单词搜索。从易到难逐步加深对剪枝的理解。全排列最简单因为选择列表明确。子集次之因为每个元素选或不选。组合总和开始有去重难度上升。括号生成的选择列表是动态的需要计数。N 皇后和单词搜索是二维回溯难度最高。7.3 面试中的注意事项面试时写回溯代码一定要先跟面试官确认三件事结果集是否需要去重、输入是否有重复元素、是否要求按特定顺序输出。这三件事直接影响剪枝逻辑。写代码时先写框架再填细节。框架就是backtrack函数签名和结束条件细节是选择列表和剪枝。这样即使写不完面试官也能看到你的思路。最后记得手动跑一个简单用例验证代码正确性。我见过太多人代码写对了但边界条件错了手动跑一遍能避免这种低级错误。提示如果面试官问「能不能不用递归」你可以说可以用栈模拟递归但代码复杂度高回溯是更自然的选择。这个回答既展示了知识面又体现了工程判断。8. 我个人的刷题体会刷完这两题我最大的收获不是学会了两个算法而是理解了「状态」和「选择」这两个概念。回溯的本质就是在状态空间里搜索每个状态有若干选择选择后进入新状态撤销后回到旧状态。这个思维模型可以迁移到很多问题比如动态规划、图搜索、甚至日常决策。另一个体会是刷题不在多而在精。这两题我刷了三遍每遍都有新理解。第一遍学会了模板第二遍学会了剪枝第三遍学会了优化。与其刷一百道题都一知半解不如把十道题刷到滚瓜烂熟。最后分享一个小技巧把这两题的代码存成模板遇到新的回溯题先复制模板再改状态定义和剪枝条件。这样能节省大量时间也能避免低级错误。我现在的回溯题代码80% 都是从这个模板改的。