回溯 = dfs + 状态重置，套路如下

做选择();
backtrack(路径, 选择列表); // 递归
撤销选择(); // 回溯，即回到上一步

收集条件：循环开始，如果条件满足题意，则收集

回溯多用于所有可能、所有排列情况，用于需要穷举的场景

由于穷举十分复杂，所以要尽可能地考虑减少穷举次数，称之为剪枝

提前排除不可能的解，减少不必要的递归调用

技巧	适用场景	实现方式	作用
1. 排序预处理	需要去重或边界检查	`Arrays.sort(nums)`	方便去重、break、上界检查
2. 早break	搜索有序数组，目标值限制	`if (candidates[i] > target) break;`	提前终止无效分支
3. used[] + 去重	含重复元素的排列/组合	`if (i>0 && nums[i]==nums[i-1] && !used[i-1]) continue;`	避免重复解
4. O(1)冲突检查	N皇后、数独等约束问题	布尔数组/位运算记录列、对角线	快速判断合法性
5. 频率检查	单词搜索、多模式匹配	字符频率统计、前缀树	提前排除不可能单词
6. DP预处理	回文分割、子串判断	`boolean[][] dp` 预处理	O(1)查询替代O(n)检查
7. 对称性剪枝	对称问题求计数	只计算一半，结果×2	减少一半搜索空间
8. 位运算优化	状态压缩、小规模问题	`int used` 代替 `boolean[]`	提升性能，减少内存
9. 结果早停	只需判断存在性	找到第一个解立即返回	避免完整搜索

一、全排列

46. 全排列↗

中等

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

示例 1：

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例 2：

输入：nums = [0,1]
输出：[[0,1],[1,0]]

示例 3：

输入：nums = [1]
输出：[[1]]

提示：

1 <= nums.length <= 6
-10 <= nums[i] <= 10
nums 中的所有整数 互不相同

1.1 交换回溯

回溯 = dfs + 状态重置，套路如下
做选择();
backtrack(路径, 选择列表); // 递归
撤销选择(); // 回溯，即回到上一步
收集条件：当倒数第二个位置确定后，整个排列就确定了，即：if (index == path.size() - 1)

先把所有数字放进一个列表path

for (每个可能放在这里的元素 i) {
    交换：把第i个元素换到 index 位置并固定
    递归：固定下一个数字(index + 1)
    交换：回溯
}

解法如下：

class Solution {

    private List<List<Integer>> res = new ArrayList<>();
    private List<Integer> path = new ArrayList<>();

    /**
     * 46. 全排列
     *
     * @param nums 提供的数组
     * @return 所有排列组合
     */
    public List<List<Integer>> permute(int[] nums) {
        for (int num: nums) {
            path.add(num);
        }
        backtrack(0);
        return res;
    }

    public void swap(int a, int b) {
        int temp = path.get(a);
        path.set(a, path.get(b));
        path.set(b, temp);
    }

    public void backtrack(int index) {
        if (index == path.size() - 1) {
            res.add(new ArrayList<>(path));
            return;
        }

        for (int i = index; i < path.size(); i++) {
            swap(i, index);
            backtrack(index + 1);
            swap(index, i);
        }
    }
}

执行用时1ms，击败96.51%，复杂度O(N!)

消耗内存44.93MB，击败11.68%，复杂度O(N)

1.2 *注意力惊人环节(heap交换)

这个看看就可以了，不推荐应用，还是用回溯法更好，可读性高，可处理重复元素

对于nums = [5, 6, 7]，我们注意到：

交换nums[0]和nums[1]，nums = [6, 5, 7]
再交换nums[1]和nums[2]，nums = [6, 7, 5]
再交换nums[2]和nums[0]，nums = [5, 7, 6]
再交换nums[0]和nums[1]，nums = [7, 5, 6]
再交换nums[1]和nums[2]，nums = [7, 6, 5]
再交换nums[2]和nums[0]，nums = [5, 6, 7]

可以发现只需要把数组变成一个环，然后不断交换nums[i % nums.length]和nums[(i + 1) % nums.length]，就可以循环遍历每一种排列可能

但是，当数组长度 > 3之后，并不能遍历每一种可能

❓根据交换的思路，有没有什么改进的办法

Heap算法（Heap’s Algorithm）是生成全排列的高效算法，由B.R. Heap于1963年提出。核心思想：通过递归和系统化的元素交换，生成所有不重复的排列。

基础情况：k=1时，只有一个排列
归纳假设：假设heap(k-1)能生成前k-1个元素的所有排列
归纳步骤：
- 先固定第k个元素，生成前k-1个元素的所有排列
- 通过循环交换，让每个元素都有机会在第k个位置
- 对每个新位置，再次生成前k-1个元素的所有排列
结论：heap(k)能生成前k个元素的所有排列

对比回溯法的优势：
- 空间效率：不需要used数组和path列表（但递归栈相同）
- 交换模式固定：在某些硬件优化场景有优势
缺点：
- 逻辑较难理解：交换策略基于奇偶性，不够直观
- 破坏原数组：最终数组会被修改
- 难以处理重复元素：对于含重复元素的排列需要额外去重逻辑
适用场景：
- 内存受限环境
- 需要流式处理排列（不存储所有结果）
- 教学和研究算法原理

class Solution {
    // 存储所有排列结果
    private List<List<Integer>> result = new ArrayList<>();
    
    public List<List<Integer>> permute(int[] nums) {
        // 调用Heap算法，从完整长度开始递归
        heap(nums.length, nums);
        return result;
    }

    /**
     * Heap算法核心递归函数
     * 
     * 算法思想（Heap's Algorithm）：
     * 1. 递归基础：当k=1时，前1个元素只有一种排列，保存当前数组
     * 2. 递归步骤：
     *    a. 先固定第k个元素，生成前k-1个元素的所有排列
     *    b. 通过交换，让每个元素都有机会在第k个位置
     *    c. 对每个新位置，再次生成前k-1个元素的所有排列
     * 
     * @param k 当前需要排列的前k个元素
     * @param nums 当前数组状态（会被原地修改）
     */
    public void heap(int k, int[] nums) {
        // 递归终止条件：只剩一个元素时，排列确定
        if (k == 1) {
            // 将当前数组转换为列表并保存
            List<Integer> list = new ArrayList<>(nums.length);
            for (int v : nums) list.add(v);
            result.add(list);
            return;
        }

        // 步骤1：先递归排列前k-1个元素（固定第k个元素在末尾）
        heap(k - 1, nums);

        // 步骤2：通过交换让每个元素都有机会在第k个位置
        for (int i = 0; i < k - 1; i++) {
            // 根据k的奇偶性决定交换策略
            if (k % 2 == 0) {
                // k为偶数：交换当前位置i和末尾位置k-1
                // 这样可以让不同位置的元素轮流到末尾
                swap(nums, i, k - 1);
            } else {
                // k为奇数：总是交换第一个位置0和末尾位置k-1
                // 这种简化交换能保证生成所有排列
                swap(nums, 0, k - 1);
            }
            // 步骤3：交换后，递归排列前k-1个元素
            heap(k - 1, nums);
        }
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

执行用时1ms，击败96.51%，复杂度O(N!)

消耗内存44.82MB，击败21.33%，复杂度O(N)(O(N)是答案返回list开销，实际额外空间O(1))

1.3 *heap流程解析

heap(4, [5,6,7,8])
│ k=4是偶数
│
├── 1. heap(3, [5,6,7,8])
│    │ k=3是奇数
│    │
│    ├── 1.1 heap(2, [5,6,7,8])              # 先递归排列前3个
│    │    │ k=2是偶数
│    │    │
│    │    ├── 1.1.1 heap(1, [5,6,7,8]) → k=1, 保存 [5,6,7,8]
│    │    │
│    │    ├── for循环 i=0: (k=2是偶数，交换 nums[0]和nums[1])
│    │    │    交换后: [6,5,7,8]
│    │    │    └── heap(1, [6,5,7,8]) → 保存 [6,5,7,8]
│    │    │
│    │    └── 循环结束，返回上层
│    │
│    ├── for循环 i=0: (k=3是奇数，交换 nums[0]和nums[2])
│    │    交换后: [7,6,5,8]
│    │    └── 1.2 heap(2, [7,6,5,8])
│    │        │ k=2是偶数
│    │        │
│    │        ├── 1.2.1 heap(1, [7,6,5,8]) → 保存 [7,6,5,8]
│    │        │
│    │        ├── for循环 i=0:
│    │        │    交换后: [6,7,5,8]
│    │        │    └── heap(1, [6,7,5,8]) → 保存 [6,7,5,8]
│    │        │
│    │        └── 循环结束
│    │
│    ├── for循环 i=1: (k=3是奇数，交换 nums[0]和nums[2])
│    │    当前数组是[6,7,5,8]，交换nums[0]和nums[2]
│    │    交换后: [5,7,6,8]
│    │    └── 1.3 heap(2, [5,7,6,8])
│    │        ├── 1.3.1 heap(1, [5,7,6,8]) → 保存 [5,7,6,8]
│    │        ├── for循环 i=0:
│    │        │    交换后: [7,5,6,8] → 保存 [7,5,6,8]
│    │        └── 循环结束
│    │
│    └── 循环结束(i<2)，返回上层
│
├── for循环 i=0: (k=4是偶数，交换 nums[0]和nums[3])
│    当前数组是[5,7,6,8]，交换后: [8,7,6,5]
│    └── 2. heap(3, [8,7,6,5])
│        │ k=3是奇数
│        │
│        ├── 2.1 heap(2, [8,7,6,5]) → 生成 [8,7,6,5] 和 [7,8,6,5]
│        │
│        ├── for循环 i=0: 交换nums[0]和nums[2] → [6,7,8,5]
│        │    └── 2.2 heap(2, [6,7,8,5]) → 生成 [6,7,8,5] 和 [7,6,8,5]
│        │
│        ├── for循环 i=1: 交换nums[0]和nums[2] → [8,7,6,5]（已存在）
│        │    └── 2.3 heap(2, [8,7,6,5]) → 生成 [8,7,6,5] 和 [7,8,6,5]
│        │
│        └── 循环结束
│
├── for循环 i=1: (k=4是偶数，交换 nums[1]和nums[3])
│    当前数组是[8,7,6,5]，交换后: [8,5,6,7]
│    └── 3. heap(3, [8,5,6,7]) → 生成6个排列...
│
├── for循环 i=2: (k=4是偶数，交换 nums[2]和nums[3])
│    当前数组是[8,5,6,7]，交换后: [8,5,7,6]
│    └── 4. heap(3, [8,5,7,6]) → 生成6个排列...
│
└── 循环结束(i<3)

二、子集

78. 子集↗

中等

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集不能包含重复的子集。你可以按 任意顺序 返回解集。

示例 1：

输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

示例 2：

输入：nums = [0]
输出：[[],[0]]

提示：

1 <= nums.length <= 10
-10 <= nums[i] <= 10
nums 中的所有元素 互不相同

2.1 回溯

回溯 = dfs + 状态重置
做选择()，即选择一个元素加入
backtrack(路径, 选择列表); // 递归
撤销选择()，即移除刚加入的元素
收集条件：因为是要所有子集，所以都收集

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    /**
     * 78. 子集
     *
     * @param nums 提供的数组
     * @return 所有子集
     */
    public List<List<Integer>> subsets(int[] nums) {
        dfs(0, nums.length, nums);
        return res;
    }

    public void dfs(int s, int l, int[] nums) {
        res.add(new ArrayList<>(path));

        for (int i = s; i < l; i++) {
            path.add(nums[i]);
            dfs(i + 1, l, nums);
            path.remove(path.size() - 1);
        }
    }
}

三、电话号码的字母组合

17. 电话号码的字母组合↗

中等

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

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

示例 1：

输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

示例 2：

输入：digits = "2"
输出：["a","b","c"]

提示：

1 <= digits.length <= 4
digits[i] 是范围 ['2', '9'] 的一个数字。

3.1 回溯

回溯 = dfs + 状态重置
做选择()，即选择当前数字所对应的按键上，其中一个字母
backtrack(路径, 选择列表); // 递归
撤销选择()，即移除所选择的字母
收集条件、剪枝：与电话号码长度相等

class Solution {

    List<String> res = new ArrayList<>();
    StringBuilder path = new StringBuilder();

    static Map<Character, String[]> map = new HashMap<>();
    static {
        map.put('2', new String[]{"a", "b", "c"});
        map.put('3', new String[]{"d", "e", "f"});
        map.put('4', new String[]{"g", "h", "i"});
        map.put('5', new String[]{"j", "k", "l"});
        map.put('6', new String[]{"m", "n", "o"});
        map.put('7', new String[]{"p", "q", "r", "s"});
        map.put('8', new String[]{"t", "u", "v"});
        map.put('9', new String[]{"w", "x", "y", "z"});
    }
    
    /**
     * 17. 电话号码的字母组合
     *
     * @param digits 号码
     * @return 所有排列组合
     */
    public List<String> letterCombinations(String digits) {
        backtrack(0, digits);
        return res;
    }

    public void backtrack(int s,  String digits) {
        if (digits.length() == s) {
            res.add(path.toString());
            return;
        }
        Character c = digits.charAt(s);
        String[] arr = map.get(c);
        for (int i = 0; i < arr.length; i++) {
            path.append(arr[i]);
            backtrack(s + 1, digits);
            path.deleteCharAt(path.length() - 1 );
        }
    }
}

四、组合总和

39. 组合总和↗

中等

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

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

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

示例 1：

输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。

示例 2：

输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]

示例 3：

输入: candidates = [2], target = 1
输出: []

提示：

1 <= candidates.length <= 30
2 <= candidates[i] <= 40
candidates 的所有元素 互不相同
1 <= target <= 40

4.1 回溯

回溯 = dfs + 状态重置
做选择()，即选择当前数字candidates[i]，并用目标值减去candidates[i]
backtrack(路径, 选择列表)，递归传递减去candidates[i]后的目标值
撤销选择()，即移除所选择的数字
收集条件、剪枝：当前目标值为0

class Solution {

    List<Integer> path = new ArrayList<>();
    List<List<Integer>> res = new ArrayList<>();
    /**
     * 39. 组合总和
     *
     * @param candidates 查找的数组
     * @param target 目标和
     * @return 所有排列组合
     */
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        backtrack(0, candidates, target);
        return res;
    }

    public void backtrack(int s, int[] candidates, int target) {
        if (target == 0) {
            res.add(new ArrayList<>(path));
            return;
        }

        for (int i = candidates.length - 1; i >= s; i--) {
            int num = candidates[i];
            if (num > target) {
                continue;
            }
            path.add(num);
            backtrack(i, candidates, target - num);
            path.remove(path.size() - 1);
        }
    }
}

五、括号生成

22. 括号生成↗

中等

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

示例 1：

输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]

示例 2：

输入：n = 1
输出：["()"]

提示：

1 <= n <= 8

5.1 回溯

回溯 = dfs + 状态重置
做选择()，即选择一种括号，每一次都可以选择左括号或者右括号
剪枝：如果左右括号数相等，当前只能选择左括号
backtrack(路径, 选择列表)
撤销选择()，即移除所选择的括号
收集条件：左右括号都用完了

class Solution {
    private List<String> ans = new ArrayList<>();
    /**
     * 22. 括号生成
     *
     * @param n 括号的对数
     * @return 所有有效的排列组合
     */
    public List<String> generateParenthesis(int n) {
        backtrack(new StringBuilder(), n, n);
        return ans;
    }

    private void backtrack(StringBuilder sb, int l, int r) {
        if (l == 0 & r == 0) {
            ans.add(sb.toString());
            return;
        }
        if (l == r) {
            sb.append("(");
            backtrack(sb, l - 1, r);
            sb.deleteCharAt(sb.length() - 1); 
        } else {
            if (r > 0) {
                sb.append(")");
                backtrack(sb, l, r - 1);
                sb.deleteCharAt(sb.length() - 1); 
            }

            if (l > 0) {
                sb.append("(");
                backtrack(sb, l - 1, r);
                sb.deleteCharAt(sb.length() - 1); 
            }
        }
    }
}

六、单词搜索

79. 单词搜索↗

中等

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

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

示例 1：

输入：board = [['A','B','C','E'],['S','F','C','S'],['A','D','E','E']], word = "ABCCED"
输出：true

示例 2：

输入：board = [['A','B','C','E'],['S','F','C','S'],['A','D','E','E']], word = "SEE"
输出：true

示例 3：

输入：board = [['A','B','C','E'],['S','F','C','S'],['A','D','E','E']], word = "ABCB"
输出：false

提示：

m == board.length
n = board[i].length
1 <= m, n <= 6
1 <= word.length <= 15
board 和 word 仅由大小写英文字母组成

进阶：你可以使用搜索剪枝的技术来优化解决方案，使其在 board 更大的情况下可以更快解决问题？

6.1 回溯

图的遍历见算法 - 扩散（2）
回溯 = dfs + 状态重置
做选择()，即访问当前节点是否为目标字母
访问完后，可以不用boolean[][] visited来记录
直接修改原数组为一个不相关符号@即可
backtrack
撤销选择()，恢复原节点
结束条件：找到一条通路即可
剪枝：结果早停

class Solution {
    /**
     * 79. 单词搜索
     *
     * @param board 字母矩阵
     * @param word  要搜索的单词
     * @return 搜索结果
     */
    public boolean exist(char[][] board, String word) {
        int h = board.length, w = board[0].length;
        
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                if (dfs(board, word, i, j, 0)) {
                    return true;
                }
            }
        }
        return false;
    }
    
    private boolean dfs(char[][] board, String word, int i, int j, int k) {
        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length) return false;
        if (board[i][j] != word.charAt(k)) return false;
        if (k == word.length() - 1) return true;
        
        board[i][j] = '@';
        
        boolean res = dfs(board, word, i+1, j, k+1) ||
                      dfs(board, word, i-1, j, k+1) ||
                      dfs(board, word, i, j+1, k+1) ||
                      dfs(board, word, i, j-1, k+1);
        
        board[i][j] = word.charAt(k);
        return res;
    }
}

执行用时134ms，击败75.47%，复杂度O(M * n ∗ 4 * L)

消耗内存42.34MB，击败34.78%，复杂度O(L)

6.2 频率检查剪枝

搜索剪枝（search pruning）：在 DFS 搜索前或搜索过程中尽早排掉不可能或不太可能产生解的分支，从而显著减少实际搜索量。

优化一：如示例 3，word =ABCB，其中字母 B 出现了 2 次，但 board[][] 中只有 1 个字母 B，所以肯定搜不到 word，直接返回 false。

以下引用自灵茶山艾府题解：第二个优化↗ 启发：如果 word=abcd 但 board 中的 a 很多，d 很少（比如只有一个），那么从 d 开始搜索，能更快地找到答案。（即使我们肉眼去找，这种方法也是更快的）

设 word 的第一个字母在 board 中出现了 x 次，word 的最后一个字母在 board 中出现了 y 次。

如果 y<x，我们可以把 word 反转，相当于从 word 的最后一个字母开始搜索，这样更容易在一开始就满足 board[i][j] != word[k]，不会往下递归，递归的总次数更少。

加上这两个优化，就可以击败接近 100% 了！其中 Java、C++、Go 和 Rust 都可以跑到 0ms。

class Solution {
    private static final int[][] DIRS = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};

    public boolean exist(char[][] board, String word) {
        // 为了方便，直接用数组代替哈希表
        int[] cnt = new int[128];
        for (char[] row : board) {
            for (char c : row) {
                cnt[c]++;
            }
        }

        // 优化一
        char[] w = word.toCharArray();
        int[] wordCnt = new int[128];
        for (char c : w) {
            if (++wordCnt[c] > cnt[c]) {
                return false;
            }
        }

        // 优化二
        if (cnt[w[w.length - 1]] < cnt[w[0]]) {
            w = new StringBuilder(word).reverse().toString().toCharArray();
        }

        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                if (dfs(i, j, 0, board, w)) {
                    return true; // 搜到了！
                }
            }
        }
        return false; // 没搜到
    }

    private boolean dfs(int i, int j, int k, char[][] board, char[] word) {
        if (board[i][j] != word[k]) { // 匹配失败
            return false;
        }
        if (k == word.length - 1) { // 匹配成功！
            return true;
        }
        board[i][j] = 0; // 标记访问过
        for (int[] d : DIRS) {
            int x = i + d[0];
            int y = j + d[1]; // 相邻格子
            if (0 <= x && x < board.length && 0 <= y && y < board[x].length && dfs(x, y, k + 1, board, word)) {
                return true; // 搜到了！
            }
        }
        board[i][j] = word[k]; // 恢复现场
        return false; // 没搜到
    }
}

执行用时0ms，击败100.00%，复杂度O(M * n * 3 ^ W)，W 为 word 的长度

消耗内存42.32MB，击败36.54%，复杂度O(M * n + W)

七、分割回文串

131. 分割回文串↗

中等

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。

示例 1：

输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]

示例 2：

输入：s = "a"
输出：[["a"]]

提示：

1 <= s.length <= 16
s 仅由小写英文字母组成

7.1 纯回溯

由于我们只关心所有字符串为回文字串的情况，若分割完不为回文串，直接跳过即可
回溯 = dfs + 状态重置
做选择()，即添加当前回文子串
backtrack，从下一位置继续分割
撤销选择()，移除当前回文字串
结束条件：处理完整个字符串
剪枝：见 7.2 DP预处理

class Solution {
    private List<List<String>> ans = new ArrayList<>();
    /**
     * 131. 分割回文串（纯回溯）
     *
     * @param s 要分割的字符串
     * @return 所有分割完且是回文串的集合
     */
    public List<List<String>> partition(String s) {
        backtrack(s, 0, new ArrayList<>());
        return ans;
    }
    
    private void backtrack(String s, int start, List<String> path) {
        // 终止条件：处理完整个字符串
        if (start == s.length()) {
            ans.add(new ArrayList<>(path));
            return;
        }
        
        // 尝试所有可能的分割点
        for (int end = start; end < s.length(); end++) {
            // 如果分割完是回文串，则加入path并继续递归
            if (isPalindrome(s, start, end)) {
                // 做选择：添加当前回文子串
                path.add(s.substring(start, end + 1));
                
                // 递归：从下一位置继续分割
                backtrack(s, end + 1, path);
                
                // 撤销选择
                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;
    }
}

执行用时8ms，击败89.06%，复杂度O(N * 2^N)

消耗内存63.88MB，击败51.38%，复杂度O(N^2)

7.2 dp + 回溯

dp见算法 - 状态（3），此处简要介绍

在纯回溯解法中，每次都要调用isPalindrome()检查子串是否是回文，这导致了大量重复计算。我们可以用动态规划预处理来O(1)时间判断任意子串是否是回文。

boolean[][] dp = new boolean[n][n];

dp[i][j]表示：从下标为i到下边为j的元素，满足某种条件

此题dp数组定义为boolean，某种条件指：s[i .. j]是否为回文串

注意到是从i到j，一定是i <= j，所以dp[][]数组中，j > i的半边没有作用

dp[i][j] = (s[i] == s[j]) && (j - i <= 2 || dp[i+1][j-1])
/*
    1. 必要条件：首尾字符相等 s[i] == s[j]
    2. 充分条件（满足其一即可）：
       a) 长度≤3：j-i ≤ 2（即长度1,2,3）
            - 长度1：单个字符，肯定是回文
            - 长度2：两个相同字符，是回文  
            - 长度3：aba型，首尾相同中间任意
       b) 去掉首尾后还是回文：dp[i+1][j-1] == true
*/

与贪心的思想（局部最优累积 -> 全局最优）类似，在此题中，如果s[i .. j]为回文串，则s[i+1 .. j-1]也为回文串、s[i+? .. j-?]也为回文串，直到i-? = j-?，即单个字符也为回文串

class Solution {
    private List<List<String>> ans = new ArrayList<>();
    private boolean[][] dp;
    /**
     * 131. 分割回文串（dp + 回溯）
     *
     * @param s 要分割的字符串
     * @return 所有分割完且是回文串的集合
     */
    public List<List<String>> partition(String s) {
        int n = s.length();
        dp = new boolean[n][n];
        
        // DP预处理：计算所有子串是否是回文
        for (int j = 0; j < n; j++) {
            for (int i = 0; i <= j; i++) {
                if (s.charAt(i) == s.charAt(j) && (j - i <= 2 || dp[i + 1][j - 1])) {
                    dp[i][j] = true;
                }
            }
        }

        backtrack(s, 0, new ArrayList<>());
        return ans;
    }
    
    private void backtrack(String s, int start, List<String> path) {
        // 终止条件：处理完整个字符串
        if (start == s.length()) {
            ans.add(new ArrayList<>(path));
            return;
        }
        
        // 尝试所有可能的分割点
        for (int end = start; end < s.length(); end++) {
            if (dp[start][end]) {
                // 做选择：添加当前回文子串
                path.add(s.substring(start, end + 1));
                
                // 递归：从下一位置继续分割
                backtrack(s, end + 1, path);
                
                // 撤销选择
                path.remove(path.size() - 1);
            }
        }
    }
}

执行用时8ms，击败89.06%，复杂度O(N^2 + N * 2^N)

消耗内存64.20MB，击败18.06%，复杂度O(N^2)

八、N 皇后

51. N 皇后↗

困难

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

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

给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

示例 1：

输入：n = 4
输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释：如上图所示，4 皇后问题存在两个不同的解法。

示例 2：

输入：n = 1
输出：[["Q"]]

提示：

1 <= n <= 9

8.1 回溯(冲突检查剪枝)

注意到：

n * n的棋盘要放置n个皇后，所以每一行、每一列一定有一个皇后
同一 \ 对角线row + column不变
同一 / 对角线row - column不变

回溯 = dfs + 状态重置
做选择()，即放置皇后，并标记以该点为中心的“米”字方向格子
backtrack，从下一位置继续分割
撤销选择()，移除皇后，取消“米”字标记
结束条件：每行都放过皇后了
剪枝：O(1) 冲突检查

class Solution {
    private List<List<String>> ans = new ArrayList<>();
    private int n;
    /**
     * 51. N 皇后
     *
     * @param n 	皇后数量
     * @return 		棋盘状况
     */
    public List<List<String>> solveNQueens(int n) {
        this.n = n;

        // 初始化棋盘
        char[][] board = new char[n][n];
        for (int i = 0; i < n; i++) Arrays.fill(board[i], '.');

        // 标记每列（column）是否已经放置皇后
        boolean[] cols = new boolean[n];
        // 标记每条方向\的对角线（diagonal）是否已经放置皇后
        boolean[] diag1 = new boolean[2 * n - 1]; 
        // 标记每条方向/的对角线（diagonal）是否已经放置皇后
        boolean[] diag2 = new boolean[2 * n - 1]; 
        backtrack(0, board, cols, diag1, diag2);
        return ans;
    }

    private void backtrack(int r, char[][] board, boolean[] cols, boolean[] diag1, boolean[] diag2) {
        // 收集结果：n行（row）都放过了
        if (r == n) {
            List<String> res = new ArrayList<>(n);
            for (int i = 0; i < n; i++) res.add(new String(board[i]));
            ans.add(res);
            return;
        }

        // 循环每列（column）
        for (int c = 0; c < n; c++) {
            int d1 = r + c;         // 同一\对角线row + column不变
            int d2 = r - c + n - 1; // 同一/对角线row - column不变，避免索引为负，再＋n
            if (cols[c] || diag1[d1] || diag2[d2]) continue;

            // 做选择：放置皇后
            board[r][c] = 'Q';
            cols[c] = true; diag1[d1] = true; diag2[d2] = true;

            // 递归，在下一行放置皇后
            backtrack(r + 1, board, cols, diag1, diag2);

            // 撤销选择
            board[r][c] = '.';
            cols[c] = false; diag1[d1] = false; diag2[d2] = false;
        }
    }
}

执行用时1ms，击败99.96%，复杂度O(N!)

消耗内存45.77MB，击败43.68%，复杂度O(N^2)

Thanks for reading!

力扣hot100-《回溯》章节题解

周五 12月 26 2025 回溯

6412 字 · 37 分钟

algorithm leetcode hot100 backtracking

Yiiyye's Blog

欲买桂花同载酒，终不似，少年游！

力扣hot100-《回溯》章节题解

一、全排列

1.1 交换回溯

1.2 *注意力惊人环节(heap交换)

1.3 *heap流程解析

二、子集

2.1 回溯

三、电话号码的字母组合

3.1 回溯

四、组合总和

4.1 回溯

五、括号生成

5.1 回溯

六、单词搜索

6.1 回溯

6.2 频率检查剪枝

七、分割回文串

7.1 纯回溯

7.2 dp + 回溯

八、N 皇后

8.1 回溯(冲突检查剪枝)

力扣hot100-《回溯》章节题解