0046.Permutations

全排列

1. 题目

1.1. 描述

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

1.2. 示例

示例 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.3. 提示

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

2. 思路

2.1. 解法一

• 设置visited数组标记循环中是否访问过元素，用dfs递归函数从头开始
• 记录已拼元素，当达到nums数组长度就得到一个全排列
• 时间复杂度为O(n!)，空间复杂度为O(n)

2.2. 解法二

• 交换nums数组中的nums[start]，nums[i]
• 时间复杂度为O(n!)，空间复杂度为O(n)

2.3. 解法三

• 数组长度为1时，数组只有一个数a₁，全排列只有一种可能即为a₁
• 数组长度为2时，数组中有两个数a₁a₂，全排列有两种可能即为a₁a₂，a₂a₁。在a₁左右插入了a₂
• 数组长度为3时，数组中有两个数a₁a₂a₃，全排列有六种可能。是在a₁a₂，a₂a₁左中右插入了a₃

2.4. 解法四

• STL 的内置函数 next_permutation()，返回下一个全排列

3. 代码

3.1. C++

3.1.1. 解法一

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        int n = nums.size();
        vector<vector<int> > ans;
        vector<int> visited(n,0);
        vector<int> perm;
        dfs(nums,0,n,visited,perm,ans);
        return ans;
    }
    void dfs(vector<int> nums,int index,int n,vector<int> visited,vector<int> perm,vector<vector<int> > &ans){
        if(index==n){
            ans.push_back(perm);
            return;
        }
        for (int i = 0; i < n; i++)
        {
            if(visited[i]==0){
                perm.push_back(nums[i]);
                visited[i]=1;
                dfs(nums,index+1,n,visited,perm,ans);
                perm.pop_back();
                visited[i]=0;
            }
        }
    }
};

3.1.2. 解法二

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

3.1.3. 解法三-递归

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        if (nums.empty()) return vector<vector<int>>(1);
        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);
                res.push_back(a);
                a.erase(a.begin() + i);
            }
        }   
        return res;
    }
};

3.1.4. 解法三-迭代

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

3.1.5. 解法四

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

3.2. Java

3.2.1. 解法一

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> visited = new LinkedList<>();
        List<Integer> perm = new LinkedList<>();
        dfs(nums,0,visited,perm,ans);
        return ans;
    }
    private void dfs(int[] nums,int index,List<Integer> visited,List<Integer> perm,List<List<Integer>> ans){
        if(index==nums.length){
            ans.add(new ArrayList<>(perm));
            return;
        }
        for (int num : nums) {
            if(visited.contains(num)==false){
                visited.add(num);
                perm.add(num);
                dfs(nums,index+1,visited,perm,ans);
                visited.remove(visited.size()-1);
                perm.remove(perm.size()-1);
            }
        }
    }
}

3.2.2. 解法二

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        dfs(nums,0,ans);
        return ans;
    }
    private void dfs(int[] nums,int index,List<List<Integer>> ans){
        if(index>=nums.length){
            List<Integer> temp = new ArrayList<>();
            for (int num : nums) {
                temp.add(num);
            }
            ans.add(temp);
            return;
        }
        for (int i = index;i<nums.length;i++) {
            swap(nums,index,i);
            dfs(nums,index+1,ans);
            swap(nums,index,i);
        }
    }
    private void swap(int[] nums,int a,int b){
        int temp = nums[a];
        nums[a] = nums[b];
        nums[b] = temp;
    }
}