Given a collection of numbers that might contain duplicates, return all possible unique permutations.
For example,
» Solve this problem[1,1,2]
have the following unique permutations:[1,1,2]
, [1,2,1]
, and [2,1,1]
.[解题思路]
跟 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.
2 comments:
dude, visited[i - 1] == 0 should be visited[i - 1] == 1, you are suppose to skip this one if it is a duplicate
Post a Comment