【LeetCode】46.全排列①

题目描述

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

示例:

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

解题思路

思路①

该题给的输入数组是没有重复项的，故该题采用递归DFS来解决，我们需要用到一个visited数组标记某个数是否访问过，然后DFS递归函数的的循环应该从头开始，为什么要用visited来标记数组中个的某个数是否用过，因为求全排列的过程中每个位置都可能放任意一个数，这样就会出现数字被重复使用。

思路②

还有一种递归的写法，比上面的简单一些，就是每次交换num里面的两个数字，经过递归可以生产所有排列情况。

思路③

第三种思路其实就是我们在数学中学过的排列组合思想，这种方法挺不错的：

当n=1时，数组中只有一个数A1；即全排列只有一种A1
当n=2时，数组此时有A1A2，其全排列只有两种，A1A2，A2A1, 那么此时我们考虑和上面那种情况的关系，我们发现，其实就是在a1的前后两个位置分别加入了A2 
当n=3时，数组中有A1A2A3，此时全排列有六种，分别为A1A2A3, A1A3A2, A2A1A3, A2A3A1, A3A1A2, 和A3A2A1。
那么根据上面的结论，实际上是在A1A2和A2A1的基础上在不同的位置上加入A3而得到的。

1
2
3

_A1_A2_ : A3A1A2, A1A3A2, A1A2A3

_A2_A1_ : A3A2A1, A2A3A1, A2A1A3

代码实现

解法一

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> ret;
        vector<int> out;
        vector<int> visited(nums.size(),0);
        premuteDFS(nums,0,visited,out,ret);
        return ret;
    }
    
    void premuteDFS(vector<int> &num,int level, vector<int> &visited,vector<int> &out,vector<vector<int>>& ret){
        if(level == num.size()){
            ret.push_back(out);
        }else{
            for(int i= 0;i<num.size();++i){
                if(visited[i] == 0){
                    visited[i] = 1;
                    out.push_back(num[i]);
                    premuteDFS(num,level+1,visited,out,ret);
                    out.pop_back();
                    visited[i] = 0;
                }   
            }
        }

    }
};

结果：

[[3,2,1],[2,3,1],[2,1,3],[3,1,2],[1,3,2],[1,2,3]]

解法二

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> ret;
       
        premuteDFS(nums,0,ret);
        return ret;
    }
    
    void premuteDFS(vector<int> &num,int start, vector<vector<int>>& ret){
        if(start >= num.size()){
            ret.push_back(num);
        }
        
        for(int i= start;i<num.size();++i){
            swap(num[start],num[i]);    
            premuteDFS(num,start+1,ret);
            swap(num[start],num[i]);
        }

    }
};

结果：

[[3,2,1],[2,3,1],[2,1,3],[3,1,2],[1,3,2],[1,2,3]]

解法三

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> ret;
        if(nums.empty()) 
            return vector<vector<int>> (1,vector<int>());
        vector<vector<int>> res;
        int first = nums[0];
        nums.erase(nums.begin());
        vector<vector<int>> words = permute(nums);
        for(auto &a:words){
            for(int i=0;i<=a.size();++i){
                a.insert(a.begin()+i,first);
                ret.push_back(a);
                a.erase(a.begin()+i);
            }
        }
        return ret;
    }
};

结果：

[[3,2,1],[2,3,1],[2,1,3],[3,1,2],[1,3,2],[1,2,3]]

上面的三种解法都是递归的，当然，还有一种方法叫迭代法，以下使用迭代的方法来做。下面这个解法就上面解法的迭代写法，核心思路都是一样的，都是在现有的排列的基础上，每个空位插入一个数字，从而生成各种的全排列的情况，参见代码如下：

解法四

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> ret{{}};
        for(int a:nums){
            for(int i=ret.size();i>0;--i){
                vector<int> t = ret.front();
                ret.erase(ret.begin());
                for(int j=0;j<=t.size();++j){
                    vector<int> one = t;
                    one.insert(one.begin()+j,a);
                    ret.push_back(one);
                }
            }
        }
        return ret;
    }
};

结果：
[[3,2,1],[2,3,1],[2,1,3],[3,1,2],[1,3,2],[1,2,3]]

解法五

还有一种解法，就是用到STL的内置函数next_permutation();
专门就是用来返回一个全排列。

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> ret;
        sort(nums.begin(),nums.end());
        ret.push_back(nums);
        while(next_permutation(nums.begin(),nums.end())){
            ret.push_back(nums);
        }
        return ret;
    }
};

结果：

[[3,2,1],[2,3,1],[2,1,3],[3,1,2],[1,3,2],[1,2,3]]