首页 > 代码库 > Permutations II <LeetCode>
Permutations II <LeetCode>
Given a collection of numbers that might contain duplicates, return all possible unique permutations.
For example,[1,1,2] have the following unique permutations:[1,1,2], [1,2,1], and [2,1,1].
思路首先按照正常的DFS算法进行计算（先进行快排），当出现一个字符等于前一个数字时，有两种方法可以解决重复 1：当出现该数字等于前一个数字时，如果前一个数字已经被使用，则该数字才可以使用，相当于对相同的数字进行一定的排序，在结果中不管这些元素在哪只能按着该次序出现，因此就避免了重复。 2：第二种方法和第一种方法相反，当出现一个数字和上一个数字相等时，如果前一个数字没有被使用，则该数字才可以使用，这样如果第一个被使用的不是相同数字中的最后一个，就不会产生一个全排列，因为这个数被使用了，它后面一个相同的数字就永远不会被使用，也相当于对相同的数字进行了排序，只不过和方法1是相反的，因此也能避免重复
1 struct tt 2 { 3 int val; 4 bool aa; 5 6 }; 7 8 class Solution { 9 public:10 vector<vector<int>> result;11 vector<tt> temp;12 vector<vector<int> > permuteUnique(vector<int> &num) {13 vector<tt> nu;14 sort(num.begin(),num.end());15 for(int i=0;i<num.size();i++)16 {17 tt t;18 t.val=num[i];19 t.aa=false;20 nu.push_back(t);21 }22 temp.clear();23 result.clear();24 getback(nu,0);25 return result;26 }27 28 void getback(vector<tt> &num,int dep)29 {30 if(dep==num.size())31 {32 vector<int> t;33 for(int i=0;i<dep;i++)34 {35 t.push_back(temp[i].val);36 }37 result.push_back(t);38 39 return;40 }41 else42 {43 for(int i=0;i<num.size();i++)44 {45 if(i>0&&num[i].val==num[i-1].val&&num[i].aa==false&&num[i-1].aa==false) //*出现相同数字时从前面的书记开始使用， 改为num[i-1].aaa==true表示从后边开始使用也可以*/46 {47 continue;48 }49 else if(num[i].aa==false)50 {51 num[i].aa=true;52 temp.push_back(num[i]);53 getback(num,dep+1);54 temp.pop_back();55 num[i].aa=false;56 }57 }58 }59 }60 };
Permutations II <LeetCode>
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。