回溯算法下篇：四道经典题讲透约束剪枝、原地标记、预计算与状态压缩

文章目录

• • 前言
  • 一、LC22 括号生成：约束剪枝
  • • 暴力枚举的问题
    • 用约束条件剪枝
  • 二、LC79 单词搜索：原地标记访问状态
  • • 错误做法：新建 visited 数组
    • 正确做法：原地标记
  • 三、LC131 分割回文串：预计算优化
  • • 基础写法：下标 + 双指针 check
    • 进阶优化：DP 预计算回文表
  • 四、LC51 N皇后：状态压缩标记
  • • 错误思路：用棋盘标记攻击范围
    • 正确思路：三个 boolean[] 记录占用状态
  • 五、四题背后的统一套路
  • • 规律一：重复子问题 → 预计算
    • 规律二：标记状态 vs 标记结果
    • 规律三：原地标记的使用边界
  • 六、写回溯前的三个检查

前言

这篇文章用四道经典回溯题——括号生成（LC22）、单词搜索（LC79）、分割回文串（LC131）、N皇后（LC51）——讲清楚回溯算法的四个核心技巧：约束剪枝、原地标记、预计算优化和状态压缩，读完你能把这些套路直接用到同类题上。

一、LC22 括号生成：约束剪枝

生成所有 n 对有效括号的组合。

暴力枚举的问题

如果暴力生成所有 2n 个位置的 ‘(’ 和 ‘)’ 排列，再过滤出有效的，时间复杂度是 O(2^(2n))。

实际上无效组合占大多数，比如 n=3 时 “))((((” 这种一看就不可能有效。

用约束条件剪枝

有效括号的两个约束：

每次递归只在满足约束时才继续，无效分支根本不走：

class Solution {
List<String> ans = new ArrayList<>();
int n;

public List<String> generateParenthesis(int n) {
this.n = n;
dfs(0, 0, new StringBuilder());
return ans;
}

public void dfs(int open, int close, StringBuilder sb) {
if (sb.length() == 2 * n) {
ans.add(sb.toString());
return;
}
// 剪枝1：左括号没用完就可以加
if (open < n) {
sb.append('(');
dfs(open + 1, close, sb);
sb.deleteCharAt(sb.length() – 1);
}
// 剪枝2：右括号数量 < 左括号才能加
if (close < open) {
sb.append(')');
dfs(open, close + 1, sb);
sb.deleteCharAt(sb.length() – 1);
}
}
}

关键：不是"生成后检查"，而是"检查后再生成"。

时间复杂度降到 O(C_n)（第 n 个卡特兰数），n=3 时从 64 次递归降到 5 次。

二、LC79 单词搜索：原地标记访问状态

在二维网格中搜索单词，每个字母只能用一次，可上下左右移动。

错误做法：新建 visited 数组

很多人会开一个 boolean[][] visited 记录访问状态，但这样每次递归都要传递或复制数组，空间浪费。

正确做法：原地标记

直接把访问过的格子临时改成特殊字符（如 '#'），回溯时再改回来：

class Solution {
char[][] board;
String word;
int m, n;

public boolean exist(char[][] board, String word) {
this.board = board;
this.word = word;
this.m = board.length;
this.n = board[0].length;

for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (dfs(i, j, 0)) return true;
}
}
return false;
}

public boolean dfs(int x, int y, int idx) {
if (idx == word.length()) return true;
if (x < 0 || x >= m || y < 0 || y >= n) return false;
if (board[x][y] != word.charAt(idx)) return false;

// 原地标记：暂存当前字符
char tmp = board[x][y];
board[x][y] = '#';

// 四个方向尝试
boolean found = dfs(x + 1, y, idx + 1) ||
dfs(x – 1, y, idx + 1) ||
dfs(x, y + 1, idx + 1) ||
dfs(x, y – 1, idx + 1);

// 回溯：恢复字符
board[x][y] = tmp;
return found;
}
}

为什么原地标记安全？

回溯保证了还原时机：每次 dfs 返回前都会执行 board[x][y] = tmp，无论是找到答案还是走不通，格子状态都会复原。

原地标记的本质是把标记信息存在数据本身，而不是额外开空间。

三、LC131 分割回文串：预计算优化

给定字符串 s，将其分割成若干子串，使每个子串都是回文串，返回所有可能的分割方案。

基础写法：下标 + 双指针 check

传统写法每次截 substring 传入下一层，代价是大量 String 对象分配。改用下标传递：

class Solution {
List<List<String>> ans = new ArrayList<>();
List<String> tmp = new ArrayList<>();
String s;

public List<List<String>> partition(String s) {
this.s = s;
dfs(0);
return ans;
}

public void dfs(int start) {
if (start == s.length()) {
ans.add(new ArrayList<>(tmp));
return;
}
for (int end = start; end < s.length(); end++) {
if (check(start, end)) {
tmp.add(s.substring(start, end + 1));
dfs(end + 1);
tmp.remove(tmp.size() – 1);
}
}
}

public boolean check(int l, int r) {
while (l < r) {
if (s.charAt(l) != s.charAt(r)) return false;
l++; r—;
}
return true;
}
}

check 直接操作原串下标，charAt() 访问内部数组，零拷贝。

进阶优化：DP 预计算回文表

check() 在不同递归分支里会对同一段 [i,j] 反复计算。用 DP 一次性算好所有区间：

dp[i][j] = true 当且仅当 s[i..j] 是回文
递推：s[i]==s[j] 且 (j-i<=2 或 dp[i+1][j-1]==true)

class Solution {
List<List<String>> ans = new ArrayList<>();
List<String> tmp = new ArrayList<>();
boolean[][] dp;
String s;

public List<List<String>> partition(String s) {
this.s = s;
int n = s.length();
dp = new boolean[n][n];
// 从右下往左上填表
for (int i = n – 1; i >= 0; i—)
for (int j = i; j < n; j++)
if (s.charAt(i) == s.charAt(j) && (j – i <= 2 || dp[i+1][j–1]))
dp[i][j] = true;
dfs(0);
return ans;
}

public void dfs(int start) {
if (start == s.length()) {
ans.add(new ArrayList<>(tmp));
return;
}
for (int end = start; end < s.length(); end++) {
if (dp[start][end]) { // O(1) 查表
tmp.add(s.substring(start, end + 1));
dfs(end + 1);
tmp.remove(tmp.size() – 1);
}
}
}
}

check 从 O(n) 降到 O(1)，对长字符串效果明显。

DP 表从右下往左上填（i 从大到小），保证计算 dp[i][j] 时 dp[i+1][j-1] 已就绪。

四、LC51 N皇后：状态压缩标记

在 n×n 棋盘上放 n 个皇后，使任意两个皇后互不攻击，返回所有解法。

错误思路：用棋盘标记攻击范围

很多人第一反应是把皇后能攻击到的格子标记成 'Q'，但这样 'Q' 就分不清"真正的皇后"和"被攻击的格子"，回溯时无法正确还原。

正确思路：三个 boolean[] 记录占用状态

棋盘只记录皇后真实位置，另用三个数组标记哪些列、对角线被占：

cols[j] = 第 j 列是否有皇后
diag1[row-col+n] = 主对角线是否有皇后（同一主对角线 row-col 相同）
diag2[row+col] = 副对角线是否有皇后（同一副对角线 row+col 相同）

class Solution {
List<List<String>> ans = new ArrayList<>();
int n;
char[][] board;
boolean[] cols, diag1, diag2;

public List<List<String>> solveNQueens(int n) {
this.n = n;
board = new char[n][n];
cols = new boolean[n];
diag1 = new boolean[2 * n];
diag2 = new boolean[2 * n];
for (char[] row : board) Arrays.fill(row, '.');
dfs(0);
return ans;
}

public void dfs(int row) {
if (row == n) {
List<String> list = new ArrayList<>();
for (char[] r : board) list.add(new String(r));
ans.add(list);
return;
}
for (int col = 0; col < n; col++) {
if (!cols[col] && !diag1[row – col + n] && !diag2[row + col]) {
board[row][col] = 'Q';
cols[col] = true;
diag1[row – col + n] = true;
diag2[row + col] = true;
dfs(row + 1);
board[row][col] = '.';
cols[col] = false;
diag1[row – col + n] = false;
diag2[row + col] = false;
}
}
}
}

每行只放一个皇后，所以 dfs 按行递推，行冲突天然不存在，只需检查列和两条对角线。

为什么用 row-col+n 做下标？

同一主对角线上的格子 row-col 值相同，但可能是负数（左下角），加 n 偏移到 [0, 2n) 范围。

五、四题背后的统一套路

规律一：重复子问题 → 预计算

LC131 的 check(i, j) 在不同分支里算的是同一段区间，本质是重叠子问题。

只要发现 DFS 里有反复调用的判断函数，就问自己：能不能提前算好存起来？

规律二：标记状态 vs 标记结果

LC51 的常见错误是把"被攻击"和"放了皇后"混存在一个数组里。

回溯的标记只应记录当前选择的状态，不能混入推导结果。

把攻击范围单独用 boolean[] 记，棋盘只存真实位置，两者职责清晰，回溯还原就不会出错。

规律三：原地标记的使用边界

LC79 能原地标记是因为：

如果数据是 final 或者没有"空值"可用（比如数字数组），就只能用额外空间。

六、写回溯前的三个检查

这三个问题想清楚，再复杂的回溯也能写对。

回溯系列完结。下一个专题：动态规划核心模型拆解。