从零开始写算法——回溯篇3:括号生成 + 单词搜索
回溯算法（DFS）是算法面试中的重难点。很多同学觉得它难，是因为分不清什么时候该“恢复现场”，什么时候该“标记状态”。
今天我们通过两道经典的 LeetCode 题目——括号生成和单词搜索，来对比分析回溯算法的两种不同模式：路径构造模式与网格搜索模式。
一、 路径构造模式：括号生成 (Generate Parentheses)
这道题是典型的“做选择”问题。你可以把它想象成手里拿着 n 个左括号和 n 个右括号，在 $2n$ 个空位上做填空题。
核心逻辑
我们在递归时需要时刻遵守两个规则，才能保证生成的括号是合法的：
手里还有存货才能放：只要左括号没用完 (
left < n)，就可以尝试放左括号。不能欠债才能还：只有当前放下的左括号多于右括号时 (
right < left)，也就是有未闭合的左括号时，才能放右括号。
代码实现
这里使用了标准的push_back和pop_back写法。这种写法的核心在于我们是在构造参数（vals），每次递归前把东西放进去，递归回来后必须把它拿出来，恢复成原来的样子，以便进行下一次选择。
C++代码实现：
class Solution { // 手里拿着 n 个左括号和 n 个右括号，做填空题，时刻遵守两个规则 // 规则1 ： left < n 规则2 ： right < left vector<string> ans; void dfs(string& vals, int left, int right, int n) { // Base Case: 左右都用完了，说明构造完成 if (right == n) { ans.push_back(vals); return; } // 尝试放左括号 if (left < n) { vals.push_back('('); // 做选择 dfs(vals, left + 1, right, n); // 进入下一层 vals.pop_back(); // 撤销选择（恢复现场） } // 尝试放右括号 if (right < left) { vals.push_back(')'); // 做选择 dfs(vals, left, right + 1, n); // 进入下一层 vals.pop_back(); // 撤销选择（恢复现场） } } public: vector<string> generateParenthesis(int n) { string vals = ""; dfs(vals, 0, 0, n); return ans; } };复杂度分析
时间复杂度：O(4^n / sqrt(n))。
这个复杂度与卡特兰数（Catalan Number）有关。简单理解，每个位置有两种选择，共有 2n 个位置，但因为有剪枝（规则限制），实际数量远小于 2^(2n)。
空间复杂度：O(n)。
主要消耗在递归调用栈和存储当前路径的
vals字符串上，最大深度为 2n。
二、 网格搜索模式：单词搜索 (Word Search)
这道题属于“图/网格遍历”。与上一题不同，这里的“恢复现场”不是为了构造字符串，而是为了防止走回头路。
核心逻辑
我们把每一个点作为起点，执行 DFS 搜索。
这里有一个非常关键的细节：什么时候标记节点？
错误做法：在进入下一层递归前，标记下一个位置 (
nx, ny)。这会导致起点无法被标记，以及逻辑判断复杂化。正确做法：标记当前位置 (
x, y)。也就是“进门后再锁门”。一旦进入 DFS 函数，先判断当前点是否匹配，匹配的话就标记为已访问（比如改为.），递归结束后再改回来。
代码实现
注意看代码中的注释，关于恢复现场和循环变量的处理是易错点。
C++代码实现：
class Solution { // 思路： 把每一个点作为起点然后对他执行dfs去遍历搜索是否存在这样的单词 // 每次上下左右找之前，把自己当前位置xy标记为. 注意是当前位置不是下一个位置 如果改的是nxny，那么下一步进去就无法通过borad[x][y] 和 word判断了 // 注意： 既然要恢复现场就要提前记录w，注意for里面不要用变量i会冲突 int dx[4] = {0, 1, 0, -1}; int dy[4] = {-1, 0, 1, 0}; bool ans; // i 代表当前匹配到了 word 的第几个字符 bool dfs(vector<vector<char>>& board, string word, int n, int i, int x, int y) { // 1. 判断当前格子字符是否匹配 if (word[i] != board[x][y]){ return false; } // 2. 匹配完成 if (i == n - 1) return true; // 3. 标记当前节点 (Backtracking 核心) // 提前记录便于恢复现场 char w = board[x][y]; // 避免重复使用到，标记为 '.' board[x][y] = '.'; // 4. 遍历四个方向 // 注意这里不能用 i 做为变量名（会与参数 i 冲突） for (int j = 0; j < 4; ++j) { int nx = x + dx[j]; int ny = y + dy[j]; // 越界检查及是否已访问检查 if (nx < 0 || nx >= board.size() || ny < 0 || ny >= board[0].size() || board[nx][ny] == '.') { continue; } // 只要有一条路走通了，就直接返回 true if (dfs(board, word, n, i + 1, nx, ny)) return true; } // 5. 恢复现场 board[x][y] = w; return false; } public: bool exist(vector<vector<char>>& board, string word) { int n = word.size(); for (int i = 0; i < board.size(); ++i) { for (int j = 0; j < board[0].size(); ++j) { // 以每个格子为起点尝试 ans = dfs(board, word, n, 0, i, j); if (ans == true) return ans; } } return ans; } };复杂度分析
时间复杂度：O(M * N * 3^L)。
M 和 N 是网格的长宽，我们需要遍历每一个格子作为起点（M * N）。
L 是字符串
word的长度。在 DFS 函数中，除了第一次有 4 个分支，之后因为不能走回头路，最多只有 3 个分支。所以是 3^L。
空间复杂度：O(L)。
空间消耗主要来自递归栈的深度，最大深度也就是单词的长度 L。
总结
通过这两道题，我们可以总结出 DFS 回溯的两个黄金法则：
构造类回溯（括号生成）：目的是拼凑出一个结果。我们通过
push_back添加元素进入下一层，出来后pop_back撤销。搜索类回溯（单词搜索）：目的是在图中寻找路径。我们通过修改
board[x][y]为特殊字符来标记“当前正在访问”，递归结束后还原字符，以免影响其他路径的搜索。
记住：每一个 DFS 函数只负责管理自己脚下的节点（标记和恢复），不要试图去管理下一层节点的标记，否则容易出现逻辑死循环。