47. 全排列 II

题目47. Permutations II类型深搜难度中等星级五星推荐版本1不同的题但是可以用同一个代码解可能这就是标准库函数的魅力吧class Solution{public:vectorvectorintpermuteUnique(vectorintnums){vectorvectorintres;sort(nums.begin(),nums.end());do{res.push_back(nums);}while(next_permutation(nums.begin(),nums.end()));returnres;}};版本2DFS考虑每个数放哪个位置如果有重复的元素必须要放在相同元素的后面这样就保证了重复元素不会重复输出class Solution{public:vectorvectorintres;vectorintpath;vectorboolst;intn;vectorvectorintpermuteUnique(vectorintnums){nnums.size();st.resize(n);path.resize(n);sort(nums.begin(),nums.end());dfs(nums,0,0);returnres;}voiddfs(vectorintnums,intu,intstart){if(un){res.push_back(path);return;}for(intistart;in;i){if(!st[i]){st[i]true;path[i]nums[u];dfs(nums,u1,u1nnums[u1]nums[u]?i1:0);st[i]false;}}}};版本32020.3.30classSolution{public:vectorvectorintres;vectorinttemp;vectorboolst;intn;vectorvectorintpermuteUnique(vectorintnums){nnums.size();st.resize(n);temp.resize(n);sort(nums.begin(),nums.end());dfs(nums,0,0);//start 用来确保相对顺序returnres;}voiddfs(vectorintnums,intu,intstart){if(un){res.push_back(temp);return;}for(intistart;in;i){if(!st[i]){st[i]true;temp[i]nums[u];dfs(nums,u1,(u1nnums[u]nums[u1])?i1:0);//相对顺序st[i]false;}}}};