Appearance
回溯与DFS/BFS
回溯是一种暴力搜索的艺术，通过"选择-递归-回溯"的模式穷举所有可能解。DFS和BFS则是图和树的两种基本遍历方式，在岛屿问题、搜索问题中应用广泛。本模块涵盖全排列、子集、组合总和、岛屿数量等经典题型，掌握回溯模板和DFS/BFS的适用场景是关键。
Q1: 全排列 「🟡 中级」
题目描述：给定一个不含重复数字的数组 nums，返回其所有可能的全排列。你可以按任意顺序返回答案。
考察点：回溯算法、排列问题、used数组标记。
解题思路：
- 方法：回溯法，用used数组标记已选元素，递归深度等于数组长度时收集结果（时间O(n*n!)，空间O(n)）- 最优解
代码实现：
java
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
backtrack(nums, new boolean[nums.length], 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!)，共n!个排列，每个排列需要O(n)复制；空间复杂度 O(n)，递归栈和used数组。
变体扩展：
- 变体1：全排列II（有重复元素）
- 变体2：第k个排列
- 变体3：下一个排列
- 变体4：字母大小写全排列
Q2: 子集 「🟡 中级」
题目描述：给你一个整数数组 nums，数组中的元素互不相同。返回该数组所有可能的子集（幂集）。解集不能包含重复的子集。你可以按任意顺序返回解集。
考察点：回溯算法、子集问题、startIndex去重。
解题思路：
- 方法1：回溯法，每次递归都收集结果，用startIndex控制不重复选择（时间O(n*2ⁿ)，空间O(n)）- 最优解
- 方法2：迭代法，逐个元素添加到已有子集中
代码实现：
java
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 startIndex, List<Integer> path, List<List<Integer>> res) {
res.add(new ArrayList<>(path)); // 每个节点都是一个子集
for (int i = startIndex; i < nums.length; i++) {
path.add(nums[i]);
backtrack(nums, i + 1, path, res);
path.remove(path.size() - 1);
}
}复杂度分析：时间复杂度 O(n*2ⁿ)，共2ⁿ个子集，每个子集复制需要O(n)；空间复杂度 O(n)，递归栈深度。
变体扩展：
- 变体1：子集II（有重复元素）
- 变体2：递增子序列
- 变体3：组合
- 变体4：所有可能的真子集
Q3: 组合总和 「🟡 中级」
题目描述：给你一个无重复元素的整数数组 candidates 和一个目标整数 target，找出 candidates 中可以使数字和为目标数 target 的所有不同组合，并以列表形式返回。你可以按任意顺序返回这些组合。candidates 中的同一个数字可以无限制重复被选取。
考察点：回溯算法、组合问题、剪枝优化。
解题思路：
- 方法：回溯法，可重复选所以startIndex从i开始（不是i+1），排序后可剪枝（时间O(n*2ⁿ)，空间O(n)）- 最优解
代码实现：
java
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> res = new ArrayList<>();
Arrays.sort(candidates); // 排序便于剪枝
backtrack(candidates, target, 0, 0, new ArrayList<>(), res);
return res;
}
private void backtrack(int[] candidates, int target, int startIndex, int sum, List<Integer> path, List<List<Integer>> res) {
if (sum == target) {
res.add(new ArrayList<>(path));
return;
}
for (int i = startIndex; i < candidates.length; i++) {
if (sum + candidates[i] > target) break; // 剪枝
path.add(candidates[i]);
backtrack(candidates, target, i, sum + candidates[i], path, res); // i不变，可重复选
path.remove(path.size() - 1);
}
}复杂度分析：时间复杂度 O(n*2ⁿ)，最坏情况所有组合都要尝试；空间复杂度 O(target/min)，递归深度最多为target/min(candidates)。
变体扩展：
- 变体1：组合总和II（每个数字只能用一次，有重复）
- 变体2：组合总和III（k个数相加等于n）
- 变体3：组合总和IV（求排列数，DP解法）
- 变体4：零钱兑换II（求组合数，DP解法）
Q4: 括号生成 「🟡 中级」
题目描述：数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且有效的括号组合。
考察点：回溯算法、括号有效性、剪枝条件。
解题思路：
- 方法：回溯法，分别追踪左右括号数量，保证左括号>=右括号（时间O(4ⁿ/√n)卡特兰数，空间O(n)）- 最优解
代码实现：
java
public List<String> generateParenthesis(int n) {
List<String> res = new ArrayList<>();
backtrack(n, n, new StringBuilder(), res);
return res;
}
private void backtrack(int left, int right, StringBuilder path, List<String> res) {
if (left == 0 && right == 0) {
res.add(path.toString());
return;
}
// 左括号还有剩余，可以选左括号
if (left > 0) {
path.append('(');
backtrack(left - 1, right, path, res);
path.deleteCharAt(path.length() - 1);
}
// 右括号多于左括号剩余时，可以选右括号（保证有效性）
if (right > left) {
path.append(')');
backtrack(left, right - 1, path, res);
path.deleteCharAt(path.length() - 1);
}
}复杂度分析：时间复杂度 O(4ⁿ/√n)，卡特兰数第n项；空间复杂度 O(n)，递归深度。
变体扩展：
- 变体1：有效的括号
- 变体2：最长有效括号
- 变体3：删除无效的括号
- 变体4：有效括号的嵌套深度
Q5: 岛屿数量 「🟡 中级」
题目描述：给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
考察点：DFS深度优先搜索、BFS广度优先搜索、网格遍历。
解题思路：
- 方法1：DFS，遍历每个格子，遇到陆地则DFS标记所有相连陆地（时间O(mn)，空间O(mn)最坏）- 最优解
- 方法2：BFS，使用队列
- 方法3：并查集
代码实现：
java
public int numIslands(char[][] grid) {
int count = 0;
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
if (grid[i][j] == '1') {
dfs(grid, i, j);
count++;
}
}
}
return count;
}
private void dfs(char[][] grid, int i, int j) {
if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] != '1') {
return;
}
grid[i][j] = '0'; // 标记为已访问
dfs(grid, i + 1, j);
dfs(grid, i - 1, j);
dfs(grid, i, j + 1);
dfs(grid, i, j - 1);
}复杂度分析：时间复杂度 O(mn)，每个格子最多访问一次；空间复杂度 O(mn)，最坏全是陆地，递归栈深度。
变体扩展：
- 变体1：岛屿的最大面积
- 变体2：岛屿的周长
- 变体3：岛屿数量II（动态添加）
- 变体4：最大人工岛
Q6: 单词搜索 「🟡 中级」
题目描述：给定一个 m x n 二维字符网格 board 和一个字符串单词 word。如果 word 存在于网格中，返回 true；否则，返回 false。单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中"相邻"单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
考察点：DFS回溯、二维网格搜索、剪枝优化。
解题思路：
- 方法：DFS回溯，从每个匹配的起点开始搜索，用标记数组或原地修改记录访问过的位置（时间O(mn3^L)，L为单词长度，空间O(L)）- 最优解
代码实现：
java
public boolean exist(char[][] board, String word) {
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
if (dfs(board, word, i, j, 0)) {
return true;
}
}
}
return false;
}
private boolean dfs(char[][] board, String word, int i, int j, int index) {
if (index == word.length()) return true;
if (i < 0 || i >= board.length || j < 0 || j >= board[0].length
|| board[i][j] != word.charAt(index)) {
return false;
}
char temp = board[i][j];
board[i][j] = '#'; // 标记已访问
boolean found = dfs(board, word, i + 1, j, index + 1)
|| dfs(board, word, i - 1, j, index + 1)
|| dfs(board, word, i, j + 1, index + 1)
|| dfs(board, word, i, j - 1, index + 1);
board[i][j] = temp; // 回溯
return found;
}复杂度分析：时间复杂度 O(mn3^L)，每个起点有3个方向可选（排除来路）；空间复杂度 O(L)，递归深度为单词长度。
变体扩展：
- 变体1：单词搜索II（Trie树优化）
- 变体2：岛屿数量
- 变体3：矩阵中的路径
- 变体4：黄金矿工
Q7: N皇后 「🔴 高级」
题目描述：按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。给你一个整数 n，返回所有不同的 n 皇后问题的解决方案。
考察点：回溯算法、经典难题、约束条件判断。
解题思路：
- 方法：回溯法，逐行放置皇后，用三个集合/数组标记列、主对角线、副对角线的占用情况（时间O(n!)，空间O(n)）- 最优解
代码实现：
java
public List<List<String>> solveNQueens(int n) {
List<List<String>> res = new ArrayList<>();
char[][] board = new char[n][n];
for (char[] row : board) Arrays.fill(row, '.');
backtrack(n, 0, board, res, new boolean[n], new boolean[2 * n - 1], new boolean[2 * n - 1]);
return res;
}
private void backtrack(int n, int row, char[][] board, List<List<String>> res,
boolean[] colUsed, boolean[] diag1Used, boolean[] diag2Used) {
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 diag1 = row - col + n - 1; // 主对角线：row-col为常数
int diag2 = row + col; // 副对角线：row+col为常数
if (colUsed[col] || diag1Used[diag1] || diag2Used[diag2]) continue;
board[row][col] = 'Q';
colUsed[col] = true;
diag1Used[diag1] = true;
diag2Used[diag2] = true;
backtrack(n, row + 1, board, res, colUsed, diag1Used, diag2Used);
board[row][col] = '.';
colUsed[col] = false;
diag1Used[diag1] = false;
diag2Used[diag2] = false;
}
}复杂度分析：时间复杂度 O(n!)，第1行n种选择，第2行最多n-2种，以此类推；空间复杂度 O(n)，递归栈和标记数组。
变体扩展：
- 变体1：N皇后II（求解的数量）
- 变体2：解数独
- 变体3：有效的数独
Q8: 二叉树的右视图 「🟡 中级」
题目描述：给定一个二叉树的根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
考察点：BFS层序遍历、DFS右优先遍历。
解题思路：
- 方法1：BFS层序遍历，每层最后一个节点就是右视图（时间O(n)，空间O(n)）- 最优解
- 方法2：DFS，根→右→左的顺序，每层第一个访问的节点加入结果
代码实现：
java
// BFS层序遍历
public List<Integer> rightSideView(TreeNode root) {
List<Integer> res = new ArrayList<>();
if (root == null) return res;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
if (i == size - 1) res.add(node.val); // 每层最后一个
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
}
return res;
}复杂度分析：时间复杂度 O(n)，每个节点入队出队一次；空间复杂度 O(n)，队列最多存最后一层节点。
变体扩展：
- 变体1：二叉树的左视图
- 变体2：二叉树的层序遍历
- 变体3：二叉树的俯视图
- 变体4：填充每个节点的下一个右侧节点指针