📝 题目描述

题目链接：全排列

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
示例 1：

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例 2：

输入：nums = [0,1]
输出：[[0,1],[1,0]]

示例 3：

输入：nums = [1]
输出：[[1]]

提示：

  • 1 <= nums.length <= 6
  • -10 <= nums[i] <= 10
  • nums 中的所有整数 互不相同

💡 解题思路

方法一：回溯

把数组里的数字想象成放在桌子上的小球，我们要把它们依次放进一个个格子里。每次挑小球时，看看哪个还没被挑走，就把它放进格子里，然后继续挑下一个。

步骤：

  • 状态记录：使用了 used 布尔数组来记录哪些数字已经被选过了，用一个 track 来记录当前已经选好的数字序列。
  • 递归填数：在每一层递归中，从头到尾遍历整个 nums 数组。
  • 剪枝与选择：如果发现 nums[i] 对应的 used[i] 为 true，说明这个数字在当前排列中已经用过了，直接跳过（continue）。否则，把它加入 track，标记为已使用（used[i] = true），然后进入下一层递归。
  • 撤销操作（回溯）：当递归返回后，把刚才加进去的数字拿出来（track.pop_back()），并且解除它的使用标记（used[i] = false），这样它就可以在后续的排列中再次被使用。

经过上面的过程，我们就可以得到全排列的结果。

🔧 代码实现

1、回溯

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
public:
    vector<vector<int>> ans;
    void backtrack(vector<bool>& used, list<int>& track, vector<int>& nums) {
        // 如果已经排列好的序列长度 = 能用的数字数量
        // 说明这是一个可能的排列组合，放入答案数组
        if (track.size() == nums.size()) {
            ans.push_back(vector<int>(track.begin(), track.end()));
            return;
        }

        // 遍历能用的数字
        for (int i = 0; i < nums.size(); i++) {
            // 用过了则跳过
            if (used[i]) {
                continue;
            }
            // 将能用的数字推入排好的序列
            track.push_back(nums[i]);
            // 标记已使用
            used[i] = true;
            // 开始选下一位的数字
            backtrack(used, track, nums);
            // 将数字拿出
            track.pop_back();
            // 标记为未使用
            used[i] = false;
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        // 设置一个标记数组，标记已经使用的数字
        vector<bool> used = vector<bool>(nums.size(), false);
        // 已经排列好的序列
        list<int> track;
        // 开始回溯
        backtrack(used, track, nums);
        return ans;
    }
};

📊 复杂度分析

1、回溯

  • 时间复杂度：O(N⋅N!)O(N⋅N!)，N! 是全排列的个数，每个排列复制到结果数组中需要 O(N)O(N) 的时间。
  • 空间复杂度：O(N)O(N)，除了 O(N)O(N) 的递归调用栈，还需要额外的 O(N)O(N) 空间用于 used 数组和 track 路径。

🎯 总结

  • 核心思想：掌握回溯法模板。