作者：jostree 转载请注明出处 http://www.cnblogs.com/jostree/p/4051169.html
题目链接：leetcode Permutations II 无重全排列
题目要求对有重复的数组进行无重全排列。为了保证不重复，类似于全排列算法使用dfs，将第一个数字与后面第一次出现的数字交换即可。例如对于序列1,1,2,2
有如下过程：
,1,2,2 -> 1,,2,2 -> 1,1,,2 -> 1,1,2,
-> 1,2,,2 -> 1,2,1,
-> 1,2,2,
-> 2,,1,2 -> 2,1,,2 -> 2,1,1,
-> 2,1,2,
-> 2,2,,1 -> 2,2,1,
代码中使用set来记录数字是否在前面出现过，如果出现过，则不与第一个数字进行交换。
代码如下：
class Solution {
public:
void swap(int &a, int &b)
{
int tmp = a;
a = b;
b = tmp;
}
void p(vector<int> &num, vector<vector<int> > &res, int begin)
{
if( begin == num.size() )
{
vector<int> tmp;
for( int i = ; i < num.size() ; i++ )
{
tmp.push_back(num[i]);
}
res.push_back(tmp);
}
else
{
set<int> used;
for( int i = begin ; i < num.size() ; i++ )
{
if(!used.count(num[i]))
{
used.insert(num[i]);
swap(num[i], num[begin]);
p(num, res, begin+);
swap(num[i], num[begin]);
}
}
}
}
vector<vector<int> > permuteUnique(vector<int> &num)
{
vector<vector<int> >res;
if( num.size() == )
{
return res;
}
sort(num.begin(), num.end());
p(num, res, );
return res;
}
};