vvrf / DSA.log

问题拆解

给一个不含重复数字的数组，返回它所有可能的全排列。

排列是逐位构造出来的：第一位有 n 种选法，选定后第二位剩 n - 1 种……这个过程天然是一棵树，从根到叶的每条路径就是一个排列。程序要做的就是遍历这棵树——用递归深入，用一条 path 记录当前走到的路径，走满 n 个数就收获一个答案。

难点在于“回头”：收获答案后要退回上一层去尝试别的分支，此时 path 和“哪些数已被用过”的状态必须精确还原，否则兄弟分支会看到脏状态。这就是回溯框架里雷打不动的三步：

做选择（把数加进 path、标记 used）→ 递归下一层 → 撤销选择（弹出 path、清除 used）。撤销必须和做选择严格镜像，一进一出配对，状态才能在整棵树上正确共享。

“哪些数用过了”可以每次线性扫 path，但用一个 used 布尔数组换成 O(1) 查询更划算——它和 path 是同一份信息的两种视图：path 记顺序，used 记成员。

used 标记 + path 回溯

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

private void backtrack(int[] nums, List<Integer> path, boolean[] used, List<List<Integer>> res) {
    if (path.size() == nums.length) {
        res.add(new ArrayList<>(path)); // 必须拷贝，path 还会被改
        return;
    }
    for (int i = 0; i < nums.length; i++) {
        if (used[i]) continue;
        path.add(nums[i]);   // 做选择
        used[i] = true;
        backtrack(nums, path, used, res);
        path.remove(path.size() - 1); // 撤销选择
        used[i] = false;
    }
}

def permute(nums: list[int]) -> list[list[int]]:
    res = []
    path = []
    used = [False] * len(nums)

    def backtrack():
        if len(path) == len(nums):
            res.append(path[:])  # 必须拷贝，path 还会被改
            return
        for i, x in enumerate(nums):
            if used[i]:
                continue
            path.append(x)      # 做选择
            used[i] = True
            backtrack()
            path.pop()          # 撤销选择
            used[i] = False

    backtrack()
    return res

func permute(nums []int) [][]int {
    res := [][]int{}
    path := make([]int, 0, len(nums))
    used := make([]bool, len(nums))

    var backtrack func()
    backtrack = func() {
        if len(path) == len(nums) {
            res = append(res, append([]int(nil), path...)) // 必须拷贝，path 还会被改
            return
        }
        for i, x := range nums {
            if used[i] {
                continue
            }
            path = append(path, x) // 做选择
            used[i] = true
            backtrack()
            path = path[:len(path)-1] // 撤销选择
            used[i] = false
        }
    }

    backtrack()
    return res
}

pub fn permute(nums: Vec<i32>) -> Vec<Vec<i32>> {
    fn backtrack(
        nums: &[i32],
        path: &mut Vec<i32>,
        used: &mut Vec<bool>,
        res: &mut Vec<Vec<i32>>,
    ) {
        if path.len() == nums.len() {
            res.push(path.clone()); // 必须拷贝，path 还会被改
            return;
        }
        for i in 0..nums.len() {
            if used[i] {
                continue;
            }
            path.push(nums[i]); // 做选择
            used[i] = true;
            backtrack(nums, path, used, res);
            path.pop();         // 撤销选择
            used[i] = false;
        }
    }

    let mut res = Vec::new();
    backtrack(&nums, &mut Vec::new(), &mut vec![false; nums.len()], &mut res);
    res
}

两个最容易翻车的点都和“共享可变状态”有关。第一，收集答案时必须拷贝 path——它是全程复用的同一个容器，直接 res.add(path) 存进去的是引用，回溯继续改动后，结果集里的所有“答案”会跟着变空。第二，撤销必须完整：path.pop() 和 used[i] = false 少写任何一个，后续分支要么排列缺数、要么某个数再也选不到。检查方法很机械——递归调用上方每写一行状态修改，下方就要有一行对应的逆操作，像括号一样配对。

另外注意循环每层都从 i = 0 扫起，而不是从某个 start 开始：排列关心顺序，[1,2] 和 [2,1] 是两个答案，靠 used 而非下标区间来避免重复选取。这是排列和组合（77）在框架上唯一的分歧点。

复杂度

指标	复杂度	原因
时间	`O(n · n!)`	共 n! 个排列，每个排列拷贝进结果集花 O(n)
空间	`O(n)`	path、used 和递归栈都是 O(n)，结果集不计

可以迁移的模式

“选择—递归—撤销”三步是所有回溯题的骨架，子集（78）、组合（77）、N 皇后（51）只是选择列表和收集时机不同；
共享容器收集答案时一律先拷贝，这个 bug 在每种带引用语义的语言里都会复发；
排列用 used 数组从头扫，组合用 start 下标向后扫——区分“顺序敏感”还是“顺序无关”，框架就定了。

把这份模板刻进肌肉记忆后，再看含重复数字的全排列 II（47），只是在 used 的基础上多加一行剪枝。