题意：
给出n个元素（可能有重复的），请产生出所有的全排列。
思路：
同版本1的有点不同，这次有可能含有重复的元素，很容易就TLE，节省时间才是关键点。
如果将一个序列中两个相同的元素交换，这个序列是仍然没有发生改变的，这也是省时间的关键点。考虑第i个位置可取的元素是nums[i-1，nums.size()-1]，那么交换的时候不必要将与num[i-1]相同的元素交换到第i位了。这可以预先通过排一次序解决。排序后变成多段相同的元素接在一起，而通常只会将每段的第一个元素被换到第i个位置，考虑每段的第2个时就会检测到相同的，自然不会交换了。
先观察一下代码的执行过程，会很好理解的。
递归：
class Solution {
vector<vector<int> > ans;
public:
void DFS(vector<int> num,int pos)//注意第一个参数不能为引用
{
if(pos+==num.size()) ans.push_back(num);
else
{
for(int i=pos; i<num.size(); i++)
{
if(i!=pos && num[i]==num[pos]) continue;//注意这里
swap(num[i],num[pos]);
DFS(num,pos+);
}
}
}
vector<vector<int> > permuteUnique(vector<int> &nums)
{
sort(nums.begin(),nums.end());
if(!nums.empty()) DFS(nums,);
return ans;
}
};
AC代码
迭代：模拟了STL中的nextPermutation函数。速度很慢。
class Solution {
public:
bool nextPermute(vector<int> &nums){
int i=nums.size()-;
while(i> && nums[i-]>=nums[i]) i-- ;//检查是否已经降序了。
if (i==) return false;
i--;
//需要在i后面找第一个比它大的来跟nums[i]交换,
int j=nums.size()-;
while(j>i && nums[j]<=nums[i]) j--;
swap(nums[i], nums[j]);//交换他们，并使这一段都是升序。
sort(nums.begin()+i+, nums.end());
return true;
}
vector<vector<int> > permuteUnique(vector<int> &nums) {
sort(nums.begin(), nums.end());
vector<vector<int>> res;
res.push_back(nums);
while (true)
{
if(!nextPermute(nums)) break;
res.push_back(nums);
}
return res;
}
};
AC代码