#46

中等

高频

回溯

全排列

这是一道围绕数组展开的高频练习。建议先掌握「回溯」这套写法，再结合下方步骤讲解理解状态维护、边界处理和复杂度取舍。

数组

原题练习

题目分析

给你一个不含重复数字的数组，要求返回它的所有排列结果。

排列的重点在于顺序不同也算不同答案，所以每个数字在每一层都可能作为当前选择。

一句话概括：

把数组里的数字按所有可能的顺序排列出来。

接下来怎么看推荐代码：带着这个理解再看推荐代码时，重点观察这条主线：用回溯逐位构造排列，每层选择一个还没用过的数字放进当前路径。

推荐代码

推荐解法：回溯

时间复杂度： O(n * n!)

空间复杂度： O(n)

核心思路：用回溯逐位构造排列，每层选择一个还没用过的数字放进当前路径。

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

    // 时间复杂度：O(n*n!)，空间复杂度：O(n)
    public void backtrack(int[] nums, List<Integer> current, List<List<Integer>> result) {
        if (current.size() == nums.length) {
            result.add(new ArrayList<>(current));
            return;
        }
        for (int num : nums) {
            if (current.contains(num)) {
                continue;
            }
            current.add(num);
            backtrack(nums, current, result);
            current.remove(current.size() - 1);
        }
    }
}

结构化讲解

面试时怎么讲

开场思路

这题我会用回溯。每一层决定当前排列的下一位放哪个数字。

核心过程

用 path 表示当前已经选好的排列前缀，用 used 记录已使用位置。
每层遍历所有未使用数字，选择一个加入路径。
递归进入下一层继续填后续位置。
返回时撤销选择，尝试这一层的其他数字。

复杂度总结

时间复杂度 O(n * n!)，空间复杂度 O(n)，不计答案存储。

面试补一句：回溯题最容易失误的地方永远是“撤销选择”。

核心思路

全排列是最标准的回溯题之一。路径里放的是当前已经选好的数字，used 数组负责保证同一个数字不会在同一条路径里被重复选择。

步骤讲解

定义路径和使用状态

用 path 记录当前已选数字顺序，用 used 标记哪些位置已经被放进路径。

为什么这样做：回溯的本质就是维护“当前决策路径”和“剩余可选项”。

对应代码提示：List path = new ArrayList<>(); boolean[] used = new boolean[n];

当前层枚举一个还没用过的数字

遍历数组，遇到未使用的数字就把它加入路径。

为什么这样做：排列要求顺序敏感，所以每一层都要尝试所有剩余数字。

对应代码提示：if (used[i]) continue;

进入下一层继续填位置

标记当前数字已使用后递归，让下一层去决定后面的数字。

为什么这样做：每次递归都意味着当前排列又确定了一位。

对应代码提示：used[i] = true; dfs(...);

返回时撤销选择

递归回来后，把最后加入的数字弹出，并恢复 used 状态。

为什么这样做：只有回到干净状态，才能尝试这一层的其他分支。

对应代码提示：path.remove(path.size() - 1); used[i] = false;

易错点

没做状态回滚

如果递归返回后不撤销选择，后续分支会带着错误状态继续运行。

正确理解：始终成对出现：先选择，再递归，最后撤销。

结果直接存 path 引用

后续回溯会继续修改 path，导致答案被一起改掉。

正确理解：加入答案时要复制当前路径。

把组合和排列写混

排列是顺序敏感的，不能只从某个起点向后枚举。

正确理解：每一层都遍历所有未使用元素，而不是只遍历后缀。

复杂度与适用判断

时间复杂度：O(n * n!)

空间复杂度：O(n)

比其他方案更好在哪里：比手工交换和多重循环更通用，扩展到子集、组合、N 皇后都沿用同一套框架。

适用判断：当题目要求枚举所有可能方案，并且每步都有选择与撤销时，优先考虑回溯。

额外提醒

排列题的状态变量通常是“当前路径 + 已使用标记”。

动画演示

如果你还没完全看懂，可以展开动画演示。

回溯动画演示

想看这段解法是怎么一步步运行的，可以展开动画继续观察。

输入数组

动画演示仅在桌面端提供，移动端请优先阅读推荐代码与结构化讲解。