回溯：系统性枚举所有可能

这一课你将能做到

1. 说出回溯三要素（选择、路径、结束条件）和标准代码骨架
2. 用 used 数组写全排列，用「选 / 不选」写子集
3. 用行列、对角线约束完成 N 皇后，并理解剪枝为什么不丢解

为什么要学

有些问题没有捷径，就是要把所有可能的方案试一遍：排列有多少种、怎么排班、棋盘怎么放、括号怎么组合。回溯就是有纪律的穷举——沿着一条路走到底，发现走不通（或已得到一个完整方案）就退回上一步，换一个选择继续。它的优雅之处在于：不用你手工管理每一种方案，只要写清楚「当前有哪些选择」，框架会自动遍历整棵决策树。

回溯在实际开发中用得少，但面试出现率不低，而且是理解深度优先搜索（DFS）、剪枝、约束满足问题的入口。更重要的是它能治好一种焦虑：面对「全部方案」类题目不再发怵，因为你有一个万能骨架。

先建立图像

把求解过程画成一棵决策树：

        根
      / | \
    选1 选2 选3        ← 每层代表「这一步的选择」
   / \   ...
 选2  选3              ← 沿一条路径走到底 = 一个完整方案
  |
 选3 → [1,2,3] 记录，然后回退换选择

万能骨架：

void backtrack(路径, 选择集):
    if 满足结束条件:
        收集一份路径的副本
        return
    for 选择 in 当前可选项:
        做选择（更新路径/标记）
        backtrack(...)
        撤销选择（恢复现场）

关键纪律两条：收集答案时存的是副本（路径之后还会被改动）；做选择和撤销选择必须严格对称。

跟着做

步骤 1：LeetCode 46「全排列」（中等）

给定不含重复数字的数组，返回所有全排列。

用 used[] 标记某数字是否已在当前路径中：每层从所有未使用的数字里选一个。

import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        boolean[] used = new boolean[nums.length];
        backtrack(nums, used, new ArrayList<>(), result);
        return result;
    }

    private void backtrack(int[] nums, boolean[] used,
                           List<Integer> path, List<List<Integer>> result) {
        if (path.size() == nums.length) {
            result.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, result);
            path.remove(path.size() - 1); // 撤销，顺序与加入时相反
            used[i] = false;
        }
    }
}

逐点讲：时间 O(n · n!)（共 n! 个排列，每个拷贝 O(n)），空间 O(n)（递归深度 + path，不计结果）。若数组含重复值（LeetCode 47），先排序，遇到 i>0 && nums[i]==nums[i-1] && !used[i-1] 时跳过即可。

步骤 2：LeetCode 78「子集」（中等）

返回数组所有子集（幂集）。

子集没有「选满」的概念——回溯树的每个节点都是一个答案，进入函数先收集；然后只从 start 位置往后选，避免出现重复组合。