Permutations II [leetcode]

防止产生重复的排列字串，即在排列时不会重复的交换

第一种思路是在递归函数中用set检查当前交换的数字是否已经换过，

如{0,1,0,2}中start=0时：

交换num[0]和num[0]，并产生start=1的子排列

交换num[0]和num[1]，并产生start=1的子排列

交换num[0]和num[2]，并产生start=1的子排列(产生重复)

交换num[0]和num[3]，并产生start=1的子排列

也可以理解为位置start只能取备选集num[start...n-1]中不同的数字

vector
  
    > permuteUnique(vector
   
     &num) { vector
    
     > res; permute(num, res, 0); return res; } void permute(vector
     
       &num, vector
      
        > & res, int start) { if (start == num.size()) { res.push_back(num); return; } set
       
         s; for (int i = start; i < num.size(); i++) { if (s.find(num[i]) == s.end()) { s.insert(num[i]); swap(num, i, start); permute(num, res, start + 1); swap(num, i, start); } } } void swap(vector
        
          &num, int i, int j) { int temp = num[i]; num[i] = num[j]; num[j] = temp; }
        
       
      
     
    
   
  

如果不用set，我们可以用一个数组visited记录当前已经选的index，并用另一个数组out存数字的顺序

此时需要对数组排序，并加上for(int curI = i; i < num.size() && num[i] == num[curI]; i++);跳过相同的数字

vector
  
    > permuteUnique(vector
   
     &num) { vector
    
     > res; vector
     
       out; vector
      
        visited(num.size()); sort(num.begin(), num.end()); permute(num, res, out, visited); return res; } void permute(vector
       
         &num, vector
        
          > & res, vector
         
          & out, vector
          
           & visited) { if (out.size() == num.size()) { res.push_back(out); return; } for (int i = 0; i < num.size(); i++) { if (!visited[i]) { visited[i] = true; out.push_back(num[i]); permute(num, res, out, visited); out.pop_back(); visited[i] = false; for(int curI = i; i < num.size() && num[i] == num[curI]; i++); i--; } } }