回溯是带撤销机制的深度优先搜索：把所有候选方案组织成一棵决策树，逐层做选择、走不通就撤回重选，用一棵树的遍历完成全量枚举。它的威力不在聪明，而在「一个不漏、一步不冤」。

它解决什么问题

有一类问题的要求很「霸道」：列出所有组合、所有排列、所有可行解，或者答案藏在巨大的搜索空间里（如 N 皇后）。这类问题没法用一个公式直接算出，只能枚举。但裸枚举的代价是指数级的：n 个元素的全排列有 n! 种，子集有 2^n 种，靠蛮力双重循环根本写不完。回溯的价值在于把枚举系统化——按树形结构逐层展开，并在每个节点做合法性检查，把不可能长出答案的整棵子树提前砍掉，一步冤枉路都不走。

核心原理

决策树模型

任何回溯问题都能画成一棵决策树：根节点是空方案，每向下一层就多做一个决定，叶子节点对应完整方案。以「从 1~3 中选 2 个数的组合」为例，第一层决定第一个数选谁，第二层在剩下的数里再挑一个，到达叶子时收集答案。所谓回溯代码，无非是对这棵树做深度优先遍历，外加一套「做完选择要记得撤销」的现场保护机制。

三要素与通用模板

动笔之前，先明确三件事：

  1. 路径（path）：已经做出的选择，即从根到当前节点的那条链。
  2. 选择列表：站在当前节点，还有哪些合法候选可以挑。
  3. 结束条件：什么时候路径构成一个完整答案，需要收集并返回。

模板因此固定为「选择 → 递归 → 撤销」的循环：

void backtrack(状态 state, List<Integer> path, List<List<Integer>> ans) {
    if (满足结束条件) {
        ans.add(new ArrayList<>(path));   // 必须拷贝快照
        return;
    }
    for (选择 choice : 当前层选择列表) {
        if (不合法) {
            continue;                     // 剪枝
        }
        path.add(choice);                 // 做选择
        backtrack(新状态, path, ans);      // 递归下一层
        path.remove(path.size() - 1);     // 撤销选择
    }
}

撤销不是形式主义的收尾：path 是整棵树复用的同一个对象，当前分支试完不还原，下一个分支就会读到脏数据。同理，收集答案时必须 new ArrayList<>(path) 拷贝一份，否则答案集里所有列表最终都指向同一个被清空的 path。

深入机制

剪枝的本质：可行性 + 最优性

剪枝只有两个正当理由，对应两类判断：

  • 可行性剪枝：当前路径已经不可能长成合法解。比如组合题中剩余元素不够凑满 k 个，循环上界可以直接收紧为 n - (k - path.size()) + 1；又比如 N 皇后中某列已被占用，该列候选直接跳过。
  • 最优性剪枝：当前路径仍有解，但注定不如已找到的答案。比如搜索最小代价路径时，当前累计代价已超过已知最优，继续深入毫无意义。

剪枝的安全前提是「被砍掉的分支里确实没有答案」。没有单调性或严格论证就乱剪，会把正确答案一并剪掉——这是回溯题最隐蔽的错误来源。排序常常能让剪枝条件更早触发，因为候选按序排列后，「后面都不行」这类判断才能成立。

排列、组合、子集：去重策略的差异

三兄弟共用同一模板，差别只在「选择列表怎么收缩」和「答案在哪里收集」：

  • 组合（LeetCode 77）：不关心顺序，用 startIndex 限定下一层只能从当前位置之后选，天然避免 [1,2] 与 [2,1] 重复。答案在 path.size() == k 时收集。
  • 排列（LeetCode 46）：关心顺序，每层都可以从全部元素里挑，用 used[] 标记哪些元素已在当前路径上，防止同一位置被重复使用。答案在路径满长时收集。
  • 子集（LeetCode 78）：树中每个节点都是合法答案，收集动作放在递归入口、结束判断之前。

输入含重复元素时，三者都要先排序，但判定条件不同。组合和子集在同一层跳过相同值即可：

if (i > startIndex && nums[i] == nums[i - 1]) {
    continue;
}

这里的 i > startIndex 很关键：它只禁止「同层重复选择」，而允许「同一路径前后选到相同值」——[1,2,2] 里的两个 2 分属不同层，是合法答案。排列更严格，要结合 used 状态：

if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
    continue;
}

含义是「前一个相同的值在本层刚被撤销、尚未进入路径」，此时选当前值必然生成与之前重复的排列；若 used[i-1] 为真，说明前一个在更早的层、属于同一路径，可以放心选。一句话总结：同层去重防重复答案，used 标记防同位置复用，两者管的不是一回事。

精讲：N 皇后

在 n×n 棋盘上放 n 个皇后，任意两个不能同行、同列、同斜线。按决策树建模：第 i 层递归对应在第 i 行选列，天然消除同行冲突，只需额外检查列与两条对角线：

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

void backtrack(int row, int n, char[][] board,
               boolean[] col, boolean[] diag1, boolean[] diag2,
               List<List<String>> ans) {
    if (row == n) {                          // n 行全部放满，收集方案
        List<String> snapshot = new ArrayList<>();
        for (char[] r : board) {
            snapshot.add(new String(r));
        }
        ans.add(snapshot);
        return;
    }
    for (int c = 0; c < n; c++) {
        int d1 = row - c + n;                // 主对角线编号
        int d2 = row + c;                    // 副对角线编号
        if (col[c] || diag1[d1] || diag2[d2]) {
            continue;                        // 可行性剪枝
        }
        board[row][c] = 'Q';
        col[c] = diag1[d1] = diag2[d2] = true;
        backtrack(row + 1, n, board, col, diag1, diag2, ans);
        board[row][c] = '.';                 // 撤销
        col[c] = diag1[d1] = diag2[d2] = false;
    }
}

两个技巧值得记住：一是用行号做递归层数，把「每行恰好一个皇后」从约束变成结构；二是对角线编号——同一主对角线上 row - col 为定值（加 n 防负下标），同一副对角线上 row + col 为定值，斜线冲突于是退化成两次数组查询，O(1) 完成检查。这题把回溯的全部要素演示了一遍：路径（棋盘）、选择列表（本行各列）、结束条件（放满 n 行）、剪枝（列与对角线冲突）。

工程实践

  • 复杂度按输出规模算：子集 2^n、排列 n!，回溯的时间下限由答案数量决定，剪枝只降常数，不改指数本质，别声称「剪枝后是多项式」。
  • 递归深度有上限：路径长度就是栈深度，n 较大时要警惕 StackOverflowError，必要时改迭代或换算法。
  • 可变状态集中管理：path、used、棋盘这类共享变量，撤销时必须精确还原；一个分支忘记恢复，错误会扩散到整棵树且极难排查。
  • 先排序再搜索：排序让重复元素相邻（便于同层去重），也让剪枝条件更早触发，几乎总是净收益。

对比与权衡

维度 回溯 动态规划 贪心
目标 枚举全部解 / 找任一可行解 求最优值或方案数 求最优值
空间结构 决策树，DFS 状态表，按依赖填 单一路径，不回看
时间复杂度 指数级（2^n、n!） 多项式 通常线性或 O(n log n)
能否反悔 能（撤销选择） 无此概念 不能
典型题 组合、排列、N 皇后 背包、子序列 区间调度、跳跃游戏

当题目只要最优值且子问题重叠，回溯枚举树中大量子树结构相同——这正是 DP 的用武之地，回溯强行求解就是指数级浪费。反过来，题目要求输出全部方案时 DP 无能为力，只能回溯。

面试视角

回溯和 DFS 是什么关系？ 回溯是 DFS 在「枚举搜索」场景下的特化写法，区别在于显式维护路径状态并强调撤销。DFS 关注遍历本身，回溯关注「做选择—深入—还原现场」的循环。

收集答案时为什么必须拷贝 path？ path 是整棵搜索树共享的可变对象，递归返回后会被撤销操作逐步清空。存引用会让答案集里的结果全部指向同一个空列表，必须存快照。

排列去重中 !used[i-1] 为什么关键？ 排序后相同元素相邻。used[i-1] 为真说明前一个在更早的层、属于同一路径，可以选；为假说明它刚在本层被撤回，当前值再选会与之前生成的排列重复，必须跳过。

组合题的 startIndex 能用 used 数组替代吗？ 可以但不必要。组合不区分顺序，用 startIndex 让选择列表单调收缩即可去重；used 能防同位置复用，但挡不住 [1,2] 与 [2,1] 这种顺序型重复。

小结

  • 回溯 = 决策树上的 DFS + 撤销机制，三要素：路径、选择列表、结束条件。
  • 剪枝只有两种合法理由：可行性（此路不通）与最优性（不如已知解），其余都是赌博。
  • 组合靠 startIndex、排列靠 used、子集每个节点收答案；含重复元素先排序，再做同层去重。
  • N 皇后是「逐行放置 + 对角线编号」两个技巧的教科书范例。
  • 模板的灵魂就九个字：做选择、递归、撤销选择。