## Saturday, December 29, 2012

### [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

[解题思路]

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