Permutations II

来源：Leetcode

原帖：http://oj.leetcode.com/problems/permutations-ii/

题目：
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].

代码：

 class Solution {  
 public:  
   vector<vector<int>> permuteUnique(vector<int> &num) {  
     vector<vector<int>> result;  
     if (num.empty()) return result;  
     sort(num.begin(), num.end());  
     vector<bool> avail(num.size(),true);  
     vector<int> onepum;  
     permuteHelper(num, onepum, avail, result);  
     return result;  
   }  
   
   void permuteHelper(const vector<int> &num, vector<int> &onepum, vector<bool> &avail, vector<vector<int> > &result) {  
     if (onepum.size() == num.size()) {  
       result.push_back(onepum);  
       return;  
     }  
     int last_index = -1;  
     for (int i = 0; i < num.size(); ++i) {  
       if (!avail[i]) continue;  
       // 1233 -> 1323  
       if (last_index != -1 && num[i] == num[last_index]) {  
         continue; // last_index stores the position been visited          
       }  
       avail[i] = false;  
       onepum.push_back(num[i]);  
       permuteHelper(num, onepum, avail, result);  
       onepum.pop_back();  
       avail[i] = true;  
       last_index = i;  
     }  
   }  
 };