Leetcode Hot 100 46.全排列
1.题目
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]]
2.答案及解析
没写出来 看答案有人用了递归
好像就是固定一个数字，和其他数字一次交换 然后递归调用自己 ？
比如说5个数字 我固定第一个 和剩下的数字交换
每次交换的时候， 剩下四个数字也这样继续递归 固定第一个然后换
然后剩下3个。。。。
最后到最后一个的时候 加入到输出里
所以应该是第一次是 第一个数字和第一个数字换 然后dfs（nums.2）
dfs（nums.2）里第二个数字和第二个数字换 然后dfs(nums,3)第三个数字和。。。
第二个和第三个数字换（因为固定了第一个数字 不和第一个换）以此类推吧
然后第二轮for 就是 第一个数字和第二个数字换了之后的数组 然后开头就变成2了 然后递归。。。
反正第一个输出的肯定是原来的数组 因为第一次换的都是自己本身
class Solution {
参数：
nums：当前排列的数组。
x：当前处理的位置。终止条件：
如果
x等于nums.size() - 1，说明已经处理完所有位置，将当前排列nums加入结果res。递归过程：
遍历从
x到nums.size() - 1的所有位置。交换
nums[i]和nums[x]，固定nums[x]，递归处理下一个位置x + 1。递归返回后，恢复交换（回溯）。
vector<vector<int>> res;
void dfs(vector<int> nums,int x){
if(x==nums.size()-1){
res.push_back(nums);
return;
}
for(int i=x;i<nums.size();i++){
swap(nums[i],nums[x]);
dfs(nums,x+1);
swap(nums[i],nums[x]);
}
}
public:
vector<vector<int>> permute(vector<int>& nums) {
dfs(nums,0);
return res;
}
};