力扣每日一题46：全排列

题目描述：

给定一个不含重复数字的数组 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]]

提示：

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

通过次数

944.6K

提交次数

1.2M

通过率

79.0%

思路和题解：

就是给你n个不重复的数字，让你把这些数字的所有排列情况给返回。

方法一：用next_permutation函数

c++在头文件里有个函数next_permutation，可以将按字母表生成的给定序列的下一个较大的排列，直到整个序列为降序为止。所以我们可以先将nums数组升序排序，排好后再使用next_permutation将每一种排序赋给返回值即可。记住刚开始一定要先给nums数组排序排成最小的，否则不会输出比nums更小的排序。

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

方法二：回溯法（递归法）

回想以下我们高中的时候计算" role="presentation" style="position: relative;">$$Ann（就是n个不同东西的排列方式有几种）怎么算的。第一个位置n个选择，然后第二个位置剩下n-1个选择......最后一个位置只有一个选择,最终结果是n*(n-1)*(n-2)*......*1。用这个思想我们可以用递归的方法以此确定每个位置放置的数字，当某个位置放某个特定的数的排列排完后，就放其他没放过的数。

代码：

vector<int> Stack; //存放每一种标记
int visited[7];    //对有没有用过第i个数进行标记
class Solution {
public:
    void dfs(vector<vector<int>>& ans,vector nums,int depth,int n)
    {
        if(depth==n)
        {//n个位置都选好了，就完成一次
            ans.emplace_back(Stack);
            return ;
        }
        for(int i=0;i<n;i++)
        {
            if(visited[i]==0)
            {
                //之前没有选过，现在就可以选了
                visited[i]=1;
                Stack.push_back(nums[i]);
                //选好depth这个位置后递归下一层选depth+1这个位置
                dfs(ans,nums,depth+1,n);
                //下一层递归结束后返回，depth这个位置重新选，堆栈的depth位置也抛出。即回溯
                //回溯的关键
                visited[i]=0;
                Stack.pop_back();
            }
        }
    }
    vector<vector<int>> permute(vector& nums) {
        int n=nums.size();
        vector<vector<int>> ans;
        for(int i=0;i<n;i++) visited[i]=0;
        dfs(ans,nums,0,n);
        return ans;
    }
};