题目描述：
给定一个不含重复数字的数组 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] <= 10nums中的所有整数 互不相同
通过次数
944.6K
提交次数
1.2M
通过率
79.0%
思路和题解：
就是给你n个不重复的数字，让你把这些数字的所有排列情况给返回。
方法一：用next_permutation函数
c++在头文件<algorithm>里有个函数next_permutation，可以将按字母表生成的给定序列的下一个较大的排列，直到整个序列为降序为止。所以我们可以先将nums数组升序排序，排好后再使用next_permutation将每一种排序赋给返回值即可。记住刚开始一定要先给nums数组排序排成最小的，否则不会输出比nums更小的排序。
class Solution {
public:vector<vector<int>> permute(vector<int>& nums) {vector<vector<int>> ans;sort(nums.begin(),nums.end());do{ans.emplace_back(nums);}while(next_permutation(nums.begin(),nums.end()));return ans;}
};方法二：回溯法（递归法）
回想以下我们高中的时候计算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<int> 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<int>& 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;}
};
