47. 全排列 II

题目：47. Permutations II
类型：深搜
难度：中等
星级：五星推荐

版本1

不同的题但是可以用同一个代码解
可能这就是标准库函数的魅力吧

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

版本2

DFS
考虑每个数放哪个位置
如果有重复的元素必须要放在相同元素的后面，这样就保证了重复元素不会重复输出

class Solution{public:vector<vector<int>>res;vector<int>path;vector<bool>st;intn;vector<vector<int>>permuteUnique(vector<int>&nums){n=nums.size();st.resize(n);path.resize(n);sort(nums.begin(),nums.end());dfs(nums,0,0);returnres;}voiddfs(vector<int>&nums,intu,intstart){if(u==n){res.push_back(path);return;}for(inti=start;i<n;i++){if(!st[i]){st[i]=true;path[i]=nums[u];dfs(nums,u+1,u+1<n&&nums[u+1]==nums[u]?i+1:0);st[i]=false;}}}};

版本3

2020.3.30

classSolution{public:vector<vector<int>>res;vector<int>temp;vector<bool>st;intn;vector<vector<int>>permuteUnique(vector<int>&nums){n=nums.size();st.resize(n);temp.resize(n);sort(nums.begin(),nums.end());dfs(nums,0,0);//start 用来确保相对顺序returnres;}voiddfs(vector<int>&nums,intu,intstart){if(u==n){res.push_back(temp);return;}for(inti=start;i<n;i++){if(!st[i]){st[i]=true;temp[i]=nums[u];dfs(nums,u+1,(u+1<n&&nums[u]==nums[u+1])?i+1:0);//相对顺序st[i]=false;}}}};