leetcode 全排列

矫情吗；* 2023-08-17 15:43 95阅读 0赞

# 一 #

> 给定一个没有重复数字的序列，返回其所有可能的全排列。

> 示例:

> 输入: \[1,2,3\]  
> 输出:  
> \[  
> \[1,2,3\],  
> \[1,3,2\],  
> \[2,1,3\],  
> \[2,3,1\],  
> \[3,1,2\],  
> \[3,2,1\]\]

> 来源：力扣（LeetCode）  
> 链接：[https://leetcode-cn.com/problems/permutations][https_leetcode-cn.com_problems_permutations]

思路：递归枚举每一个位置上放哪个数。

class Solution {
    public:
        int n;
        vector<vector<int>> ans;
        vector<int> path;
        vector<bool> st;
        vector<vector<int>> permute(vector<int>& nums) {
            n=nums.size();
            st=vector<bool>(n);
            dfs(nums,0);
            return ans;
        }
        void dfs(vector<int>& nums,int u)
        {
            if(u==n){
                ans.push_back(path);
                return ;
            }
            for(int i=0;i<n;++i){
                if(!st[i]){
                    path.push_back(nums[i]);
                    st[i]=true;
                    dfs(nums,u+1);
                    path.pop_back();
                    st[i]=false;
                }
            }
        }
    };

# 二 #

> 给定一个可包含重复数字的序列，返回所有不重复的全排列。

> 示例:

> 输入: \[1,1,2\]  
> 输出:  
> \[  
> \[1,1,2\],  
> \[1,2,1\],  
> \[2,1,1\]\]

> 来源：力扣（LeetCode）  
> 链接：[https://leetcode-cn.com/problems/permutations-ii][https_leetcode-cn.com_problems_permutations-ii]

思路：同1，不过这里会有重复数字，这里枚举第一位的时候如果第一个1用过了，那麽第二个1不能用，这里可以用prev记录前一个用的是哪个数，下一个和它一样就不能再用了。  
知识点：vector不能做key值

class Solution {
    public:
        int n;
        vector<vector<int>> ans;
        vector<int> path;
        vector<bool> st;
        
        vector<vector<int>> permuteUnique(vector<int>& nums) {
            n=nums.size();
            st=vector<bool>(n);
            sort(nums.begin(),nums.end());
            dfs(nums,0);
            return ans;
        }
        void dfs(vector<int> & nums,int u){
            if(u==n){
                ans.push_back(path);
                return;
            }
            int prev=-1e9;
            for(int i=0;i<n;++i){
                if(!st[i]&&(nums[i]!=prev)){
                    st[i]=true;
                    prev=nums[i];
                    path.push_back(nums[i]);
                    dfs(nums,u+1);
                    st[i]=false;
                    path.pop_back();
                }
            }
        }
    };

转载于:https://www.cnblogs.com/clear-love/p/11346318.html

[https_leetcode-cn.com_problems_permutations]: https://leetcode-cn.com/problems/permutations
[https_leetcode-cn.com_problems_permutations-ii]: https://leetcode-cn.com/problems/permutations-ii