Backtracking 回溯算法

一、什么是回溯算法回溯算法本质上是一种递归搜索算法。它会尝试所有可能的选择当发现某条路径不合适时就退回上一步换另一种选择继续尝试。可以理解为回溯 深度优先搜索 DFS 状态撤销 剪枝例如生成括号n 3我们要生成所有合法的 3 对括号((())) (()()) (())() ()(()) ()()()但是不能生成这些非法情况())(( ))(( (()))所以回溯算法不仅要“尝试”还要“判断能不能尝试”。二、这道题的核心思想对于每一个位置我们都有两种可能选择放左括号 ( 放右括号 )但是不能随便放。对于 n 对括号1. 左括号最多只能放 n 个例如 n 3最多只能放(((所以代码中有if (open n)意思是如果左括号数量还没到 n就可以继续放左括号。2. 右括号数量不能超过左括号数量例如())这是非法的因为在某个位置上右括号数量已经超过左括号了。合法括号必须满足任意前缀中右括号数量 左括号数量所以代码中有if (close open)意思是只有当前右括号数量小于左括号数量时才能放右括号。比如当前是((open 2close 0可以放右括号(()但是当前是()open 1close 1此时不能再直接放右括号因为会变成())这是非法的。三、代码中的变量含义你的回溯函数是void backtrack(vectorstring result, string current, int open, int close, int n)每个参数的作用如下参数含义result保存最终所有合法结果current当前正在构造的括号字符串open当前已经使用的左括号数量close当前已经使用的右括号数量n一共需要生成几对括号例如current (() open 2 close 1 n 3说明当前已经生成了(()里面有 2 个左括号1 个右括号。四、回溯函数整体逻辑你的核心代码是void backtrack(vectorstring result, string current, int open, int close, int n) { if (current.size() 2 * n) { result.push_back(current); return; } if (open n) { current.push_back((); backtrack(result, current, open 1, close, n); current.pop_back(); } if (close open) { current.push_back()); backtrack(result, current, open, close 1, n); current.pop_back(); } }可以拆成三部分。1. 递归终止条件if (current.size() 2 * n) { result.push_back(current); return; }因为 n 对括号一共有2 * n个字符。例如 n 3((()))长度是 6。当current.size() 6时说明已经生成了一个完整的括号组合。由于前面递归过程中已经保证了括号合法所以这里可以直接加入结果。2. 尝试放左括号if (open n) { current.push_back((); backtrack(result, current, open 1, close, n); current.pop_back(); }这部分表示如果左括号还没用完就尝试添加一个左括号。比如当前current (( open 2 close 0 n 3因为open n也就是2 3所以还可以继续放左括号current (((然后进入下一层递归。递归回来之后执行current.pop_back();把刚才放进去的(删除。这就是回溯中的“撤销选择”。3. 尝试放右括号if (close open) { current.push_back()); backtrack(result, current, open, close 1, n); current.pop_back(); }这部分表示只有右括号数量小于左括号数量时才能添加右括号。例如当前current (() open 2 close 1因为close open 1 2所以可以继续放右括号current (())但是如果当前current () open 1 close 1此时close open 1 1不成立所以不能继续放右括号。否则就会变成())这是非法的。五、为什么要pop_back()这是学习回溯最关键的地方。比如这段代码current.push_back((); backtrack(result, current, open 1, close, n); current.pop_back();假设当前current (我们添加一个左括号current ((然后进入递归继续生成所有以((开头的情况。当这些情况都生成完之后我们要退回到current (然后尝试其他选择比如添加右括号current ()如果不执行pop_back()那么current会一直保留之前添加的字符后面的分支就会被污染。所以pop_back()的作用是把当前路径恢复到进入这一层递归之前的状态。这就是“回溯”这个名字的来源。六、以 n 3 为例看递归过程刚开始current open 0 close 0第一步只能放左括号(因为不能一开始放右括号否则会变成)非法。然后继续( ├── (( │ ├── ((( │ │ └── ((() │ │ └── ((()) │ │ └── ((())) │ └── (() │ ├── (()( │ │ └── (()() │ │ └── (()()) │ └── (()) │ └── (())( │ └── (())() └── () └── ()( ├── ()(( │ └── ()(() │ └── ()(()) └── ()() └── ()()( └── ()()()最后得到((())) (()()) (())() ()(()) ()()()七、这段代码为什么不会生成非法括号因为它在递归过程中做了两个限制。限制一左括号不能超过 n 个if (open n)防止生成((((这种左括号太多的情况。限制二右括号不能超过左括号if (close open)防止生成()) )((这种右括号提前过多的情况。所以这道题不是先生成所有字符串再判断是否合法而是在生成过程中就把非法情况剪掉了。这就是回溯算法里的剪枝。八、回溯算法模板以后你遇到排列、组合、子集、括号生成、棋盘搜索这类题都可以用这个模板思考void backtrack(路径, 选择列表, 状态参数) { if (满足结束条件) { 保存结果; return; } for (选择 : 选择列表) { if (选择不合法) { continue; } 做选择; backtrack(路径, 选择列表, 新状态); 撤销选择; } }而你的括号生成代码虽然没有明显的for循环但本质上有两个选择选择 1放 ( 选择 2放 )所以它等价于if (可以放左括号) { 放左括号; 递归; 撤销左括号; } if (可以放右括号) { 放右括号; 递归; 撤销右括号; }九、把你的代码加上更详细注释#include iostream #include vector #include string using namespace std; class Solution { public: vectorstring generateParenthesis(int n) { vectorstring result; // 用来保存所有合法的括号组合 string current; // 当前正在构造的括号字符串 // 从空字符串开始搜索 // open 表示已经使用的左括号数量 // close 表示已经使用的右括号数量 backtrack(result, current, 0, 0, n); return result; } private: void backtrack(vectorstring result, string current, int open, int close, int n) { // 递归终止条件 // 当 current 的长度等于 2 * n说明已经放满 n 对括号 if (current.size() 2 * n) { result.push_back(current); // 保存当前合法组合 return; } // 选择一尝试放左括号 // 只要左括号数量还没有达到 n就可以继续放左括号 if (open n) { current.push_back((); // 做选择加入左括号 backtrack(result, current, open 1, close, n); // 进入下一层递归此时左括号数量加 1 current.pop_back(); // 撤销选择删除刚刚加入的左括号 } // 选择二尝试放右括号 // 只有右括号数量小于左括号数量时才能放右括号 // 这样可以保证任意位置上都不会出现右括号比左括号多的非法情况 if (close open) { current.push_back()); // 做选择加入右括号 backtrack(result, current, open, close 1, n); // 进入下一层递归此时右括号数量加 1 current.pop_back(); // 撤销选择删除刚刚加入的右括号 } } };十、这道题对应的回溯三要素1. 路径当前已经生成的字符串current例如(()2. 选择当前位置可以选择放(或者)3. 结束条件当字符串长度达到2 * n说明生成完成。if (current.size() 2 * n)十一、时间复杂度和空间复杂度这道题生成的是所有合法括号组合。合法括号组合数量是一个经典数量叫做卡特兰数。当 n 11 个结果当 n 22 个结果当 n 35 个结果当 n 414 个结果当 n 542 个结果所以结果数量增长很快。时间复杂度可以理解为O(结果数量 × 每个结果的长度)也就是大约O(Cn × n)其中Cn是第 n 个卡特兰数。空间复杂度主要是递归栈和当前字符串O(n)如果算上保存结果的空间则是O(Cn × n)十二、学习回溯时最重要的一句话你可以把这道题的回溯过程理解成我每一步都尝试放一个括号如果能放左括号就放左括号继续递归如果能放右括号就放右括号继续递归当前路径走完后撤销刚才的选择回到上一步尝试另一条路。十三、这段代码的核心精华真正体现回溯思想的是这两组代码current.push_back((); backtrack(result, current, open 1, close, n); current.pop_back();和current.push_back()); backtrack(result, current, open, close 1, n); current.pop_back();它们分别表示做选择 继续搜索 撤销选择这是所有回溯题的核心结构。十四、你可以这样记忆回溯算法遇到回溯题先问自己四个问题1. 当前路径是什么本题中是current2. 当前可以做哪些选择本题中是放 ( 放 )3. 什么情况下不能继续本题中是open n close open不过你的代码直接用if避免了这些非法情况。4. 什么情况下保存答案本题中是current.size() 2 * n十五、总结这道题的回溯逻辑可以总结成一句话在保证括号合法的前提下递归尝试每一个位置放 ( 或 )当字符串长度达到 2n 时保存结果。你的代码是一个非常标准的回溯写法做选择 递归 撤销选择其中open n控制左括号数量不超标。close open控制右括号不会提前过多。current.pop_back()负责回到上一层状态继续尝试其他可能。掌握这道题之后再学组合、排列、子集、N 皇后、单词搜索这类题会容易很多。