[LeetCode] 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].

» Solve this problem

[解题思路]
跟 Permutations的解法一样，就是要考虑“去重”。先对数组进行排序，这样在DFS的时候，可以先判断前面的一个数是否和自己相等，相等的时候则前面的数必须使用了，自己才能使用，这样就不会产生重复的排列了。

与Permitations的code相比，只加了3行，Line 8，23，24。

[Code]

1:    vector<vector<int> > permuteUnique(vector<int> &num) {  
2:      // Start typing your C/C++ solution below  
3:      // DO NOT write int main() function  
4:      vector<vector<int> > coll;  
5:      vector<int> solution;  
6:      if(num.size() ==0) return coll;  
7:      vector<int> visited(num.size(), 0);  
8:      sort(num.begin(), num.end());  
9:      GeneratePermute(num, 0, visited, solution, coll);  
10:      return coll;  
11:    }  
12:    void GeneratePermute(vector<int> & num, int step, vector<int>& visited, vector<int>& solution, vector<vector<int> >& coll)  
13:    {  
14:      if(step == num.size())  
15:      {  
16:        coll.push_back(solution);  
17:        return;  
18:      }  
19:      for(int i =0; i< num.size(); i++)  
20:      {  
21:        if(visited[i] == 0)  
22:        {  
23:          if(i>0 && num[i] == num[i-1] && visited[i-1] ==0)  
24:            continue;  
25:          visited[i] = 1;  
26:          solution.push_back(num[i]);  
27:          GeneratePermute(num, step+1, visited, solution, coll);  
28:          solution.pop_back();  
29:          visited[i] =0;  
30:        }  
31:      }  
32:    }  

[Note]
Line 23: Don't miss “&& visited[i-1] ==0”. Or, the inner recursion will skip using duplicate number.