本文共 1054 字，大约阅读时间需要 3 分钟。

47.全排列II

给定一个可包含重复数字的序列，返回所有不重复的全排列

• 与46不同的是，这里有可能有重复数字导致重复排列，解决办法
• 先排序，在DFS的时候加一个剪枝的条件：如果当前数组与前一个数字相等且前一个标志位为0（即未被使用，就意味着以这个数字开头的排列已经存在于结果数组，也就是回溯过了）

class Solution {
   public:    vector
   
    
     > permuteUnique(vector
     
      & nums) {
           if(nums.size() == 0) return {
   };        sort(nums.begin(),nums.end());        vector
      
       
         > res;        vector
        
          tmp; vector
         
           flag(nums.size(),0); DFS(res,tmp,flag,nums); return res; } void DFS(vector
          
           
             > &res,vector
            
              &tmp,vector
             
               &flag,vector
              
                nums){ if(tmp.size() == nums.size()){ res.push_back(tmp); } for(int i = 0;i < nums.size();i++){ if(flag[i] == 1 || (i>0 && flag[i-1] == 0 && nums[i] == nums[i-1])) continue; flag[i]=1; tmp.push_back(nums[i]); DFS(res,tmp,flag,nums); tmp.pop_back(); flag[i]=0;//不要忘了回溯的时候置回0 } }};
              
             
            
           
          
         
        
       
      
     
    
   

通过时间：

转载地址：http://bsemb.baihongyu.com/