回溯

回溯算法的核心在于递归 + 状态重置。通过构建决策树来寻找所有解。

17. 电话号码的字母组合 (Letter Combinations of a Phone Number)

题目描述

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

电话按键映射

解题思路

DFS 递归决策树。

建立数字到字母列表的映射 HashMap。
递归深度为数字字符串的长度。
每一层尝试映射到的字符串里的所有可能字母。
加入 StringBuilder -> 递归 dfs(index + 1) -> 回溯（删除最后一位）。

Java 代码实现

class Solution {
    List<String> res = new ArrayList<>();
    String[] map = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    public List<String> letterCombinations(String digits) {
        if (digits.length() == 0) return res;
        dfs(digits, 0, new StringBuilder());
        return res;
    }
    private void dfs(String digits, int idx, StringBuilder sb) {
        if (idx == digits.length()) { res.add(sb.toString()); return; }
        for (char c : map[digits.charAt(idx) - '0'].toCharArray()) {
            sb.append(c);
            dfs(digits, idx + 1, sb);
            sb.deleteCharAt(sb.length() - 1);
        }
    }
}

77. 组合 (Combinations)

题目描述

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按 任意顺序 返回答案。

解题思路

控制起始位置的 DFS。从 start 开始遍历到 n。

list.add(i) -> dfs(n, k, i + 1, list) -> list.removeLast()。
剪枝优化：如果当前 list 长度加上剩余可选长度 < k，直接返回。

Java 代码实现

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> combine(int n, int k) {
        dfs(n, k, 1, new ArrayList<>());
        return res;
    }
    private void dfs(int n, int k, int start, List<Integer> list) {
        if (list.size() == k) { res.add(new ArrayList<>(list)); return; }
        for (int i = start; i <= n - (k - list.size()) + 1; i++) { // 剪枝
            list.add(i);
            dfs(n, k, i + 1, list);
            list.remove(list.size() - 1);
        }
    }
}

46. 全排列 (Permutations)

题目描述

给定一个不含重复数字的数组 nums ，返回其所有可能的全排列。你可以按 任意顺序 返回答案。

解题思路

Used 数组记录状态。

全排列的核心是控制已使用的数字。
维护 boolean[] used。
递归 n 层，每一层遍历数组，如果没用过则使用，递归到下一层后再撤销状态。

Java 代码实现

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> permute(int[] nums) {
        dfs(nums, new boolean[nums.length], new ArrayList<>());
        return res;
    }
    private void dfs(int[] nums, boolean[] used, List<Integer> list) {
        if (list.size() == nums.length) { res.add(new ArrayList<>(list)); return; }
        for (int i = 0; i < nums.length; i++) {
            if (!used[i]) {
                used[i] = true; list.add(nums[i]);
                dfs(nums, used, list);
                used[i] = false; list.remove(list.size() - 1);
            }
        }
    }
}

39. 组合总和 (Combination Sum)

题目描述

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。

对于给定的输入，保证和为 target 的不同组合数少于 150 个。

解题思路

可重用数字的 DFS。

排序 candidates 方便提前剪枝。
递归时，传入 i 而不是 i + 1，表示当前数字可以继续用。
如果 target < 0 返回。

Java 代码实现

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        dfs(candidates, target, 0, new ArrayList<>());
        return res;
    }
    private void dfs(int[] cands, int t, int start, List<Integer> list) {
        if (t == 0) { res.add(new ArrayList<>(list)); return; }
        for (int i = start; i < cands.length; i++) {
            if (t - cands[i] < 0) break; // 剪枝
            list.add(cands[i]);
            dfs(cands, t - cands[i], i, list);
            list.remove(list.size() - 1);
        }
    }
}

52. N 皇后 II (N-Queens II)

题目描述

n 皇后问题 研究的是如何将 n 个皇后放置在 n × n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回 n 皇后问题 不同的解的数量。

解题思路

行列及对角线状态标记。

使用三个 boolean 数组或 set 记录哪些列、正对角线、负对角线 已经被占用。
对于位置 (r, c)：
- 列下标为 c。
- 正对角线（右上到左下）下标为 r + c。
- 负对角线（左上到右下）下标为 r - c。
逐行放置皇后，若当前位置满足条件，标记状态并进入下一行，递归归来后重置状态。

Java 代码实现

class Solution {
    int res = 0;
    public int totalNQueens(int n) {
        dfs(n, 0, new boolean[n], new boolean[2 * n], new boolean[2 * n]);
        return res;
    }
    private void dfs(int n, int r, boolean[] cols, boolean[] d1, boolean[] d2) {
        if (r == n) { res++; return; }
        for (int c = 0; c < n; c++) {
            int id1 = r + c, id2 = r - c + n;
            if (cols[c] || d1[id1] || d2[id2]) continue;
            cols[c] = d1[id1] = d2[id2] = true;
            dfs(n, r + 1, cols, d1, d2);
            cols[c] = d1[id1] = d2[id2] = false;
        }
    }
}

22. 括号生成 (Generate Parentheses)

题目描述

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

解题思路

有效性约束回溯。

记录左括号剩余数量 left 和右括号剩余数量 right。
规则一：只要 left > 0，就可以放置左括号。
规则二：只要 right > left，说明当前右括号比左括号少放了，可以放置右括号（保持有效性）。
当 left == 0 && right == 0 时得到完整组合。

Java 代码实现

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<>();
        dfs(n, n, new StringBuilder(), res);
        return res;
    }
    private void dfs(int left, int right, StringBuilder sb, List<String> res) {
        if (left == 0 && right == 0) {
            res.add(sb.toString());
            return;
        }
        if (left > 0) {
            sb.append('(');
            dfs(left - 1, right, sb, res);
            sb.deleteCharAt(sb.length() - 1);
        }
        if (right > left) {
            sb.append(')');
            dfs(left, right - 1, sb, res);
            sb.deleteCharAt(sb.length() - 1);
        }
    }
}

79. 单词搜索 (Word Search)

题目描述

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使用。

解题思路

网格 DFS + 状态原位回溯。

遍历网格起点，开启 DFS。
在 DFS 过程中，检查当前位置字符是否匹配 word 的第 k 位。
如果匹配，将当前字符修改为特殊标记（如 '#'）防止 DFS 过程中重复访问。
递归四个方向。
回溯：递归结束后，必须将字符复原。

Java 代码实现

class Solution {
    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[][] b, String w, int r, int c, int k) {
        if (k == w.length()) return true;
        if (r < 0 || r >= b.length || c < 0 || c >= b[0].length || b[r][c] != w.charAt(k)) return false;
        
        char tmp = b[r][c];
        b[r][c] = '#';
        boolean res = dfs(b, w, r + 1, c, k + 1) || dfs(b, w, r - 1, c, k + 1) ||
                      dfs(b, w, r, c + 1, k + 1) || dfs(b, w, r, c - 1, k + 1);
        b[r][c] = tmp;
        return res;
    }
}

17. 电话号码的字母组合 (Letter Combinations of a Phone Number)​

题目描述​

解题思路​

Java 代码实现​

77. 组合 (Combinations)​

题目描述​

解题思路​

Java 代码实现​

46. 全排列 (Permutations)​

题目描述​

解题思路​

Java 代码实现​

39. 组合总和 (Combination Sum)​

题目描述​

解题思路​

Java 代码实现​

52. N 皇后 II (N-Queens II)​

题目描述​

解题思路​

Java 代码实现​

22. 括号生成 (Generate Parentheses)​

题目描述​

解题思路​

Java 代码实现​

79. 单词搜索 (Word Search)​

题目描述​

解题思路​

Java 代码实现​

17. 电话号码的字母组合 (Letter Combinations of a Phone Number)

题目描述

解题思路

Java 代码实现

77. 组合 (Combinations)

题目描述

解题思路

Java 代码实现

46. 全排列 (Permutations)

题目描述

解题思路

Java 代码实现

39. 组合总和 (Combination Sum)

题目描述

解题思路

Java 代码实现

52. N 皇后 II (N-Queens II)

题目描述

解题思路

Java 代码实现

22. 括号生成 (Generate Parentheses)

题目描述

解题思路

Java 代码实现

79. 单词搜索 (Word Search)

题目描述

解题思路

Java 代码实现