回溯算法概述
回溯算法（Backtracking）本质是 暴力穷举 + 剪枝优化，它通过深度优先搜索（DFS）遍历所有可能的解空间，并在搜索过程中利用约束条件提前终止无效分支（剪枝）。回溯的核心模板是：
void backtrack(路径, 选择列表) {
if (满足终止条件) {
记录结果;
return;
}
for (选择 : 选择列表) {
做选择;
backtrack(路径, 新的选择列表);
撤销选择; // 回溯核心
}
}
回溯算法适用于 排列、组合、子集、分割、棋盘 等经典问题。LeetCode 热门 100 题中有八道回溯题，覆盖了回溯的绝大多数应用场景。下面按逻辑分组逐一拆解。
一、子集与组合（78、39）
78. 子集
题目：给定不含重复元素的整数数组，返回所有可能的子集（幂集）。
核心思路：经典选/不选模型，或用 start 控制不回头遍历。每次递归都将当前路径加入结果，然后从 start 开始循环，选择下一个元素。
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
backtrack(nums, 0, new ArrayList<>(), res);
return res;
}
private void backtrack(int[] nums, int start, List<Integer> path, List<List<Integer>> res) {
res.add(new ArrayList<>(path));
for (int i = start; i < nums.length; i++) {
path.add(nums[i]);
backtrack(nums, i + 1, path, res);
path.remove(path.size() - 1);
}
}
复杂度：时间 O(n * 2^n)（每个子集复制开销），空间 O(n)（递归栈）。
关键点：res.add(new ArrayList<>(path)) 在每次递归开始时记录，包含空集；i + 1 保证元素不重复使用。
39. 组合总和
题目：给定无重复元素数组和目标值，找出所有和为目标值的组合（元素可重复使用）。
核心思路：与子集类似，但递归时传递 i 而非 i+1 以允许重复使用当前元素，并通过 target - nums[i] 剪枝（提前排序可进一步剪枝）。
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> res = new ArrayList<>();
Arrays.sort(candidates); // 便于剪枝
backtrack(candidates, target, 0, new ArrayList<>(), res);
return res;
}
private void backtrack(int[] candidates, int target, int start, List<Integer> path, List<List<Integer>> res) {
if (target == 0) {
res.add(new ArrayList<>(path));
return;
}
for (int i = start; i < candidates.length; i++) {
if (candidates[i] > target) break; // 剪枝
path.add(candidates[i]);
backtrack(candidates, target - candidates[i], i, path, res); // 注意是 i 不是 i+1
path.remove(path.size() - 1);
}
}
复杂度：时间取决于解的数量（最坏指数级），空间 O(n)。
关键点：允许重复使用元素体现在递归参数 i 而非 i+1；排序后通过 candidates[i] > target 提前终止循环。
二、排列（46）
46. 全排列
题目：给定不含重复元素的数组，返回所有可能的全排列。
核心思路：使用 used[] 数组标记哪些元素已被选择。与组合不同的是，排列每次循环都从 0 开始，但跳过已使用的元素。
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
boolean[] used = new boolean[nums.length];
backtrack(nums, used, new ArrayList<>(), res);
return res;
}
private void backtrack(int[] nums, boolean[] used, List<Integer> path, List<List<Integer>> res) {
if (path.size() == nums.length) {
res.add(new ArrayList<>(path));
return;
}
for (int i = 0; i < nums.length; i++) {
if (used[i]) continue;
used[i] = true;
path.add(nums[i]);
backtrack(nums, used, path, res);
path.remove(path.size() - 1);
used[i] = false;
}
}
复杂度：时间 O(n * n!)，空间 O(n)。
关键点：排列与组合的本质区别在于是否关注顺序；排列用 used 数组，组合用 start 索引。
三、字符串映射与剪枝（17、22）
17. 电话号码的字母组合
题目：给定数字字符串（2-9），返回其能表示的所有字母组合（如电话键盘）。
核心思路：构建数字到字母串的映射，DFS 遍历 digits，每层取当前数字对应的字母进行拼接。
public List<String> letterCombinations(String digits) {
List<String> res = new ArrayList<>();
if (digits == null || digits.length() == 0) return res;
String[] map = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
backtrack(digits, map, 0, new StringBuilder(), res);
return res;
}
private void backtrack(String digits, String[] map, int idx, StringBuilder sb, List<String> res) {
if (idx == digits.length()) {
res.add(sb.toString());
return;
}
String letters = map[digits.charAt(idx) - '0'];
for (char c : letters.toCharArray()) {
sb.append(c);
backtrack(digits, map, idx + 1, sb, res);
sb.deleteCharAt(sb.length() - 1);
}
}
复杂度：时间 O(4^n * n)，空间 O(n)。
关键点：这是典型的"多叉树"回溯，每一层的分支数取决于按键对应的字母数。
22. 括号生成
题目：给定 n，生成所有可能的且有效的括号组合（n 对括号）。
核心思路：维持左右括号数量，left 和 right 都等于 n 时终止。约束条件：左括号数不超过 n，右括号数不超过左括号数。
public List<String> generateParenthesis(int n) {
List<String> res = new ArrayList<>();
backtrack(n, 0, 0, new StringBuilder(), res);
return res;
}
private void backtrack(int n, int left, int right, StringBuilder sb, List<String> res) {
if (left == n && right == n) {
res.add(sb.toString());
return;
}
if (left < n) {
sb.append('(');
backtrack(n, left + 1, right, sb, res);
sb.deleteCharAt(sb.length() - 1);
}
if (right < left) {
sb.append(')');
backtrack(n, left, right + 1, sb, res);
sb.deleteCharAt(sb.length() - 1);
}
}
复杂度：时间 O(4^n / √n)（卡特兰数），空间 O(n)。
关键点：right < left 是核心剪枝条件，保证括号有效性；这也是回溯中"剪枝"的经典体现。
四、矩阵回溯（79）
79. 单词搜索
题目：给定二维字符网格和单词，判断单词是否存在于网格中（相邻格子水平或垂直连接，不能重复使用同一格）。
核心思路：遍历每个格子作为起点，DFS 搜索匹配单词。用 board[i][j] = '#' 或 visited 数组标记已访问，匹配失败则回溯还原。
public boolean exist(char[][] board, String word) {
int m = board.length, n = board[0].length;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (dfs(board, word, 0, i, j)) return true;
}
}
return false;
}
private boolean dfs(char[][] board, String word, int idx, int i, int j) {
if (idx == word.length()) return true;
if (i < 0 || i >= board.length || j < 0 || j >= board[0].length) return false;
if (board[i][j] != word.charAt(idx)) return false;
char temp = board[i][j];
board[i][j] = '#'; // 标记已访问
boolean found = dfs(board, word, idx + 1, i - 1, j) ||
dfs(board, word, idx + 1, i + 1, j) ||
dfs(board, word, idx + 1, i, j - 1) ||
dfs(board, word, idx + 1, i, j + 1);
board[i][j] = temp; // 回溯还原
return found;
}
复杂度：时间 O(m * n * 3^L)（L 为单词长度，分支因子为 3 因为不会往回走），空间 O(L)。
关键点：矩阵回溯需要在递归前"标记"当前格子，递归后"还原"，防止重复使用；四个方向用短路或（||）连接。
五、分割（131）
131. 分割回文串
题目：给定字符串，将其分割成若干子串，使每个子串都是回文串，返回所有可能的分割方案。
核心思路：从起始位置 start 开始，枚举结束位置 end，若子串 [start, end] 是回文，则将其加入路径，递归处理剩余部分。
public List<List<String>> partition(String s) {
List<List<String>> res = new ArrayList<>();
backtrack(s, 0, new ArrayList<>(), res);
return res;
}
private void backtrack(String s, int start, List<String> path, List<List<String>> res) {
if (start == s.length()) {
res.add(new ArrayList<>(path));
return;
}
for (int end = start; end < s.length(); end++) {
if (isPalindrome(s, start, end)) {
path.add(s.substring(start, end + 1));
backtrack(s, end + 1, path, res);
path.remove(path.size() - 1);
}
}
}
private boolean isPalindrome(String s, int left, int right) {
while (left < right) {
if (s.charAt(left++) != s.charAt(right--)) return false;
}
return true;
}
复杂度：时间最坏 O(n * 2^n)，空间 O(n)。
关键点：分割问题的"选择列表"是当前起点到末尾的所有回文子串；用双指针判断回文，也可用 DP 预处理优化。
六、棋盘（51）
51. N 皇后
题目：在 n×n 棋盘上放置 n 个皇后，使其不能互相攻击（不同行、列、对角线），返回所有合法摆法。
核心思路：逐行放置皇后，用三个集合分别记录已占用的列、主对角线（row - col）、副对角线（row + col）。每行在可放置的列中尝试。
public List<List<String>> solveNQueens(int n) {
List<List<String>> res = new ArrayList<>();
boolean[] cols = new boolean[n];
boolean[] diag1 = new boolean[2 * n - 1]; // row - col + n - 1
boolean[] diag2 = new boolean[2 * n - 1]; // row + col
char[][] board = new char[n][n];
for (char[] row : board) Arrays.fill(row, '.');
backtrack(n, 0, cols, diag1, diag2, board, res);
return res;
}
private void backtrack(int n, int row, boolean[] cols, boolean[] diag1, boolean[] diag2,
char[][] board, List<List<String>> res) {
if (row == n) {
List<String> list = new ArrayList<>();
for (char[] r : board) list.add(new String(r));
res.add(list);
return;
}
for (int col = 0; col < n; col++) {
int d1 = row - col + n - 1;
int d2 = row + col;
if (cols[col] || diag1[d1] || diag2[d2]) continue;
board[row][col] = 'Q';
cols[col] = diag1[d1] = diag2[d2] = true;
backtrack(n, row + 1, cols, diag1, diag2, board, res);
board[row][col] = '.';
cols[col] = diag1[d1] = diag2[d2] = false;
}
}
复杂度：时间 O(n!)，空间 O(n²)（棋盘存储）。
关键点：主对角线 row - col 为定值，副对角线 row + col 为定值；通过偏移 + n - 1 保证索引非负。
八题对比与总结
| 题目 | 解空间类型 | 核心剪枝/去重 | 递归参数 | 时间复杂度 |
|---|---|---|---|---|
| 78 子集 | 组合/子集 | start 去重 |
start |
O(n * 2^n) |
| 39 组合总和 | 组合（可重复） | 排序 + candidate > target |
start（允许自身） |
O(解的数量) |
| 46 全排列 | 排列 | used[] 标记 |
used[] |
O(n * n!) |
| 17 电话组合 | 映射多叉树 | 无（天然无重复） | idx（位置） |
O(4^n * n) |
| 22 括号生成 | 约束生成 | right < left |
left, right 计数 |
O(4^n / √n) |
| 79 单词搜索 | 矩阵路径 | 原地标记 # |
i, j 坐标 |
O(mn * 3^L) |
| 131 回文分割 | 分割 | 回文检测 | start 起点 |
O(n * 2^n) |
| 51 N 皇后 | 棋盘放置 | 列/对角线集合 | row 行号 |
O(n!) |
共同本质：回溯的核心是 “做出选择 → 递归 → 撤销选择”。无论问题形式如何，都可抽象为"遍历决策树"，通过约束条件剪枝。
总结心法：
- 确定递归函数的参数（通常是"当前处理位置"或"剩余目标"）。
- 确定终止条件（满足要求时记录结果）。
- 确定选择列表（当前层有哪些可选分支）。
- 确定剪枝条件（跳过不符合要求的分支）。
- 确定是否需要去重（组合用
start，排列用used）。