Backtracking 回溯算法
一、什么是回溯算法？
回溯算法本质上是一种递归搜索算法。
它会尝试所有可能的选择，当发现某条路径不合适时，就退回上一步，换另一种选择继续尝试。
可以理解为：
回溯 = 深度优先搜索 DFS + 状态撤销 + 剪枝
例如生成括号：
n = 3我们要生成所有合法的 3 对括号：
((())) (()()) (())() ()(()) ()()()但是不能生成这些非法情况：
())(( ))(( (()))所以回溯算法不仅要“尝试”，还要“判断能不能尝试”。
二、这道题的核心思想
对于每一个位置，我们都有两种可能选择：
放左括号 '(' 放右括号 ')'但是不能随便放。
对于 n 对括号：
1. 左括号最多只能放 n 个
例如 n = 3，最多只能放：
(((所以代码中有：
if (open < n)意思是：
如果左括号数量还没到 n，就可以继续放左括号。
2. 右括号数量不能超过左括号数量
例如：
())这是非法的，因为在某个位置上，右括号数量已经超过左括号了。
合法括号必须满足：
任意前缀中，右括号数量 <= 左括号数量所以代码中有：
if (close < open)意思是：
只有当前右括号数量小于左括号数量时，才能放右括号。
比如当前是：
((open = 2，close = 0，可以放右括号：
(()但是当前是：
()open = 1，close = 1，此时不能再直接放右括号，因为会变成：
())这是非法的。
三、代码中的变量含义
你的回溯函数是：
void backtrack(vector<string>& 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(vector<string>& 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: vector<string> generateParenthesis(int n) { vector<string> result; // 用来保存所有合法的括号组合 string current; // 当前正在构造的括号字符串 // 从空字符串开始搜索 // open 表示已经使用的左括号数量 // close 表示已经使用的右括号数量 backtrack(result, current, 0, 0, n); return result; } private: void backtrack(vector<string>& 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 = 1：
1 个结果当 n = 2：
2 个结果当 n = 3：
5 个结果当 n = 4：
14 个结果当 n = 5：
42 个结果所以结果数量增长很快。
时间复杂度可以理解为：
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 皇后、单词搜索这类题会容易很多。