leetcode 46. 全排列(经典)

​
​

作者简介：C/C++ 、Golang 领域耕耘者，创作者
个人主页：作者主页
活动地址：CSDN21天学习挑战赛
题目来源： leetcode官网
如果感觉博主的文章还不错的话，还请关注➕ 、点赞👍 、收藏🧡三连支持一下博主哦~~~

💜 题目描述

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

示例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]]

🧡 算法分析

此题方法是用dfs

该题就是一颗深度优先遍历的一颗树，我们的将它递归树枚举的状态画出来就是下面的样子

那么我们应该想需要什么状态， 实际上这里就是函数的参数
分析得： 需要知道填什么数字（vector 数组）、需要记录填到哪一位（int u 下标）、需要知道哪位数组已经填过了（标记数组bool st）

算法步骤：

1. 从前往后，一位一位枚举，每次选择一个没有被使用过的数。
2. 选好之后，将该数的状态改成“已被使用”，同时将该数记录在相应位置上，然后递归。
3. 递归返回时，不要忘记将该数的状态改成“未被使用”，并将该数从相应位置上删除。

💚 代码实现

class Solution {
public:
    vector<vector<int>> re;
    vector<int> path;
    vector<bool> st;

    vector<vector<int>> permute(vector<int>& nums) {
        st = vector<bool>(nums.size());
        path = vector<int>(nums.size());
        dfs(nums, 0);
        return re;
    }

    void dfs(vector<int>& nums, int u)
    {
        if(u == nums.size()) 
        {
            re.push_back(path);
            return;
        }

        for(int i = 0; i < nums.size(); i ++)
        {
            if (!st[i]) 
            {
                //path.push_back(nums[i]);
                path[u] = nums[i]; 
                st[i] = true;
                dfs(nums, u + 1);
                // path.pop_back();
                path[u] = -1;   // 恢复现场， 可以不需要，因为后面会覆盖掉
                st[i] = false;
            }
        }
    }
};
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

下面实现跟上面差不多，数组形式改了

class Solution {
public:
    vector<vector<int>> re;
    vector<int> path;
    vector<bool> st;

    vector<vector<int>> permute(vector<int>& nums) {
        st = vector<bool>(nums.size());
        dfs(nums, 0);
        return re;
    }

    void dfs(vector<int>& nums, int u)
    {
        if(u == nums.size()) 
        {
            re.push_back(path);
            return;
        }

        for(int i = 0; i < nums.size(); i ++)
        {
            if (!st[i]) 
            {
                path.push_back(nums[i]);
                st[i] = true;
                dfs(nums, u + 1);
                path.pop_back();   // 恢复现场
                st[i] = false;
            }
        }
    }
};
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

执行结果：

💙 时间复杂度分析

O(n * n !)
搜索树中最后一层共 n!个叶节点，在叶节点处记录方案的计算量是 O(n)，所以叶节点处的计算量是 O(n×n!)。

如果觉得对你有帮助的话:
👍 点赞，你的认可是我创作的动力！
🧡 收藏，你的青睐是我努力的方向！
✏️ 评论，你的意见是我进步的财富！