全排列 图解题解

这道题到底在问什么

nums

[1, 2, 3]

输出

6 种排列

先想最直接的笨办法

进第二层，枚举从头开始：想选 1？它已经在路径里了，used[0]=True，打叉跳过，看下一个。这就是代码里 if used[i]: continue 那一行在画面上的样子。（动画第 6 步）

最优解：一步一步想明白

1. 3想象你在一层层做决定：每层挑一个还没用过的数放进路径 path；path 凑满 3 个就记下来；然后撤销刚才的选择，回到上一层换一个数继续。
2. 4path 空路径 path 一开始是空的，三个数都没用过，结果 res 也是空。
3. 5path = [1]第一层先选 1：标记 1 已用，放进 path。path = [1]。
4. 6used[0]=True · 跳过进第二层，枚举从头开始：想选 1？它已经在路径里了，used[0]=True，打叉跳过，看下一个。这就是代码里 if used[i]: continue 那一行在画面上的样子。
5. 7path = [1,2]还是这一层，往后继续枚举：跳过 1 之后轮到 2，选它。path = [1, 2]。
6. 8path = [1,2,3]第三层只剩 3，选它。path = [1, 2, 3]，凑满 3 个了！
7. 9res ← [1,2,3]path 长度等于 3，记下这个排列 [1,2,3]。然后开始往回退（回溯）。
8. 10path = [1,2]撤销刚才的 3：把它移出 path、标记为没用过。回到第二层，可这层除了 3 没别的可选了，继续往上退。
9. 11path = [1]撤销 2，回到 path = [1]。第一层选过 1 后，第二层还能换成 3 试试。
10. 12path = [1,3]这次第二层选 3。path = [1, 3]。
11. 13res ← [1,3,2]第三层只剩 2，凑满 [1, 3, 2]，记下来。以 1 开头的排列全找完了。
12. 14path 空继续撤销，一直退回 path 为空。现在换第一个数，不选 1 了。
13. 15path = [2]第一层改选 2——注意 used 只有 2 亮着，1 和 3 都被撤销复位了，所以它俩在下面又能被选。撤销谁、什么时候撤销正是回溯能换分支的关键。1 开头那条已逐帧讲透，这条同构，只看结果。
14. 16res ← [2,1,3] · [2,3,1]2 之后只剩 1、3：先 1 后 3 得 [2,1,3]；撤销到 [2]、第二层换 3，再得 [2,3,1]。和 1 开头一模一样的「选→递归→收集→撤销」，不再逐帧重画。
15. 17path = [3]2 开头穷举完，撤到 used 全空，第一层选最后一个 3。剩下 1、2 接着排。
16. 18res ← [3,1,2] · [3,2,1]同样的套路：3 后选 1 再选 2 得 [3,1,2]；撤回 [3] 换 2 得 [3,2,1]。六种全部到齐。
17. 196 种排列撤销到底、path 清空，6 种排列不重不漏全部找齐。这就是回溯的威力：系统地穷举所有可能。
18. 22它没有任何数学技巧，就是把每条路都走一遍；唯一的巧妙是「撤销」让一份 path 反复复用，省下重新构造的成本。子集、组合、N 皇后……都是它的变体。
19. 25path 只增不减亲眼看一次塌方：收完 [1,2,3] 后如果漏了 pop，path 还撑着 3 个数退不回去，第二种排列 [1,3,2] 根本没机会被装进 path——res 永远只收得到这一份。这就是上一帧雷区、也是下面小测 2 的考点。
20. 28把这题练到能复述后，再去同类题里迁移：先复用状态定义，再调整边界条件。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

class Solution:
    def permute(self, nums):
        ans = []
        used = [False] * len(nums)
        def backtrack(path):
            if len(path) == len(nums):
                ans.append(path[:])
                return
            for i, x in enumerate(nums):
                if used[i]:
                    continue
                used[i] = True
                path.append(x)
                backtrack(path)
                path.pop()
                used[i] = False
        backtrack([])
        return ans

class Solution {
    vector<vector<int>> ans;
    vector<int> path;
public:
    void dfs(vector<int>& nums, vector<int>& used) {
        if (path.size() == nums.size()) { ans.push_back(path); return; }
        for (int i = 0; i < nums.size(); i++) {
            if (used[i]) continue;
            used[i] = 1; path.push_back(nums[i]);
            dfs(nums, used);
            path.pop_back(); used[i] = 0;
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        vector<int> used(nums.size(), 0);
        dfs(nums, used);
        return ans;
    }
};

class Solution {
    List<List<Integer>> ans = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    void dfs(int[] nums, boolean[] used) {
        if (path.size() == nums.length) { ans.add(new ArrayList<>(path)); return; }
        for (int i = 0; i < nums.length; i++) {
            if (used[i]) continue;
            used[i] = true; path.add(nums[i]);
            dfs(nums, used);
            path.remove(path.size() - 1); used[i] = false;
        }
    }
    List<List<Integer>> permute(int[] nums) {
        boolean[] used = new boolean[nums.length];
        dfs(nums, used);
        return ans;
    }
}

def backtrack(path):
    if 满足结束条件:
        res.append(path[:])   # 注意 [:] 拷贝
        return
    for 选择 in 选择列表:
        if 不能选: continue
        做选择(path)          # append + used=True
        backtrack(path)
        撤销选择(path)        # pop + used=False

void backtrack(状态& path) {
    if (满足结束条件) {
        ans.push_back(path);   // 整份拷贝
        return;
    }
    for (auto& 选择 : 选择列表) {
        if (不能选) continue;
        做选择(path);          // push + used=true
        backtrack(path);
        撤销选择(path);        // pop + used=false
    }
}

void backtrack(List<状态> path) {
    if (满足结束条件) {
        ans.add(new ArrayList<>(path));  // new 一份拷贝
        return;
    }
    for (选择 : 选择列表) {
        if (不能选) continue;
        做选择(path);          // add + used=true
        backtrack(path);
        撤销选择(path);        // remove + used=false
    }
}

复杂度

面试官可能追问