首页 > 代码库 > Permutations II
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].
思路：先对num进行排序，然后直接调用标准库的next_permutation函数求解。
1 class Solution { 2 public: 3 vector<vector<int>> permuteUnique( vector<int> &num ) { 4 vector<vector<int>> permutations; 5 sort( num.begin(), num.end() ); 6 permutations.push_back( num ); 7 while( next_permutation( num.begin(), num.end() ) ) { 8 permutations.push_back( num ); 9 }10 return permutations;11 }12 };
使用DFS求解。
1 class Solution { 2 public: 3 vector<vector<int>> permuteUnique( vector<int> &num ) { 4 vector<vector<int>> permutations; 5 sort( num.begin(), num.end() ); 6 PermuteSub( 0, num, permutations ); 7 return permutations; 8 } 9 private:10 void PermuteSub( int s, vector<int> &num, vector<vector<int>> &permutations ) {11 int size = num.size();12 if( s >= size-1 ) { permutations.push_back( num ); return; }13 PermuteSub( s+1, num, permutations );14 for( int i = s + 1; i < size; ++i ) {15 if( num[s] != num[i] && num[i-1] != num[i] ) {16 swap( num[s], num[i] );17 PermuteSub( s+1, num, permutations );18 swap( num[s], num[i] );19 }20 }21 sort( num.begin()+s, num.end() );22 return;23 }24 };
Permutations II
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。