[LeetCode]全排列I，II

全排列I

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

思路：

对于递归问题，很多时候动笔画一画，答案就出来的差不多了，区别就是每一层干的事不一样。递归问题里可以将一些变量设为全局的，减少传参，方便一点。

将vector<vector<int>> ret和vector<int> path 设为全局

全排列I每层要干的事即：遍历nums数组，如果之前没用过，就插入到path数组中，直到path的大小跟nums一样，就将path插入到ret数组

涉及快速查找之前是否使用过，那这里就要用哈希。用unordered系列就有点夸张了，因为nums每个数字都是不重复的，所以搞个同等规模的bool check[n]即可，标记对应位置是否之前使用过

别搞个unordered_set<int> hash，hash.insert(nums[i])来查找，太小巫见大巫了

使用过就continue，换下一个数字来——这里就是所谓的剪枝操作

代码： 

class Solution {vector<vector<int>> ret;vector<int> path;//unordered_set<int> hash;bool check[7];int n;
public:vector<vector<int>> permute(vector<int>& nums) {n=nums.size();dfs(nums);return ret;}   void dfs(vector<int>& nums){if(path.size()==n){ret.push_back(path);return;}for(int i=0;i<n;i++){//被使用过if(check[i]) continue;//没被使用过path.push_back(nums[i]);check[i]=true;dfs(nums);path.pop_back();check[i]=false;}}};

全排列II

给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

示例 1：

输入：nums = [1,1,2]
输出：
[[1,1,2],[1,2,1],[2,1,1]]

示例 2：

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

思路：这里nums的元素是可以重复的，示例1的前两个1虽然值相等，但是不是真正的同一个数字。相对于全排列I，其实就是多了一个剪枝操作

1.同一个节点不使用值相同的数字

2.同一个数字不能被重复使用

代码：

class Solution {vector<vector<int>> ret;vector<int> path;bool check[9];//unordered_set<int> isExist;int n;
public:void dfs(vector<int>& nums){if(path.size()==n){ret.push_back(path);return;}for(int i=0;i<n;i++){//if(isExist.count(nums[i])) break;//同一层中不使用相同的数字——去重//先将数组排序if(check[i]||(i!=0&&nums[i]==nums[i-1]&&check[i-1]==false)) continue;path.push_back(nums[i]);check[i]=true;dfs(nums);path.pop_back();check[i]=false;}}vector<vector<int>> permuteUnique(vector<int>& nums) {sort(nums.begin(),nums.end());n=nums.size();dfs(nums);return ret;}
};