Permutations

46. 全排列

分析

思路
- 每次递归选择一个未使用的数字加入当前路径，直到路径长度等于数组长度，记录当前排列
初始化
- 用 res 保存最终的所有排列结果
- 用 path 保存当前排列路径
- 用布尔数组 is_used 标记某个数字是否已被使用，避免重复选择
回溯逻辑 dfs
- 如果当前路径长度 u 等于数组长度，保存当前路径到结果集 res 中
- 遍历数组，对未使用的数字：
  - 标记为已使用
  - 将数字加入路径
  - 递归进入下一层
  - 回溯时取消标记并移除路径中的数字

时间复杂度

时间复杂度：O(n!)，因为共有 n! 种排列

空间复杂度

空间复杂度：O(n)，递归调用栈深度为 n，path 和 is_used 数组均为 O(n)

C++代码

 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:
    std::vector<std::vector<int>> res;   // 存储最终结果
    std::vector<int> path;              // 当前排列路径
    std::vector<bool> is_used;          // 标记是否使用过当前数字

    vector<vector<int>> permute(vector<int>& nums)
    {
        // 初始化 path 和 is_used 数组
        path = std::vector<int>(nums.size());
        is_used = std::vector<bool>(nums.size());

        // 调用回溯函数
        dfs(nums, 0);
        return res;
    }

    void dfs(std::vector<int>& nums, int u)
    {
        // 如果路径长度等于数组长度，保存结果
        if (u == nums.size())
        {
            res.push_back(path);
            return;
        }

        // 遍历所有数字，尝试加入当前路径
        for (int i = 0; i < nums.size(); ++i)
        {
            if (!is_used[i]) {           // 如果当前数字未使用
                is_used[i] = true;      // 标记当前数字已使用
                path[u] = nums[i];      // 加入当前路径
                dfs(nums, u + 1);       // 递归生成下一个位置的数字
                is_used[i] = false;     // 回溯时取消标记
            }
        }
    }
};