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)

每个参数的作用如下：

例如：

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. 当前路径是什么？

本题中是：

current

2. 当前可以做哪些选择？

本题中是：

放 '(' 放 ')'

3. 什么情况下不能继续？

本题中是：

open > n close > open

不过你的代码直接用if避免了这些非法情况。

4. 什么情况下保存答案？

本题中是：

current.size() == 2 * n

十五、总结

这道题的回溯逻辑可以总结成一句话：

在保证括号合法的前提下，递归尝试每一个位置放 '(' 或 ')'，当字符串长度达到 2n 时保存结果。

你的代码是一个非常标准的回溯写法：

做选择 递归 撤销选择

其中：

open < n

控制左括号数量不超标。

close < open

控制右括号不会提前过多。

current.pop_back()

负责回到上一层状态，继续尝试其他可能。

掌握这道题之后，再学组合、排列、子集、N 皇后、单词搜索这类题会容易很多。