首页 > 代码库 > leetcode-Permutations II-47

leetcode-Permutations II-47

输入一个数组,字典序输出所有排列,输入的数组中元素可能有重复。

详细思路看上一篇博文,这里重点说一下去重:

上一篇的去重不完善,思路是完善的,代码不完善,加了一个判断才对,具体看代码注释

 1 class Solution { 2 public: 3     void func(vector<vector<int> > &v,vector<int> a,int low,int high){ 4         if(low==high-1){ 5             v.push_back(a); 6             return; 7         } 8         for(int i=low;i<high;i++){ 9             if(i!=low&&a[i]==a[low]||(i>0&&i!=low&&a[i]==a[i-1])) continue;  //这里的||后面的判断才是真正判断同一层中一个相同值的元素只递归一次10             swap(a[i],a[low]);11             sort(a.begin()+low+1,a.end());12             func(v,a,low+1,high);13             swap(a[i],a[low]);14         }15     }16     vector<vector<int>> permuteUnique(vector<int>& nums) {17         vector<vector<int> > v;18         sort(nums.begin(),nums.end());19         func(v,nums,0,nums.size());20         return v;21     }22 };

 

leetcode-Permutations II-47