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].
思路：有重复数字的情况，之前在Subsets II，我们采取的是在某一个递归内，用for循环处理所有重复数字。这里当然可以将数组排序，然后使用该方法。
而另一种方法是不排序，在一个递归内申请一个set，用来判断该数字是否已经在当前depth出现过。
class Solution { public: vector<vector<int> > permuteUnique(vector<int> &num) { result.clear(); sort(num.begin(),num.end()); dfs(num, 0); return result; } void dfs(vector<int> num, int depth) { if(depth == num.size()-1) { result.push_back(num); return; } dfs(num,depth+1); set<int> flag; //用来判断当前数字是否在depth位置出现过 flag.insert(num[depth]); int temp = num[depth]; for(int i = depth+1; i< num.size(); i++) { if(flag.find(num[i])!=flag.end()) continue; flag.insert(num[i]); num[depth]=num[i]; num[i] = temp; dfs(num,depth+1); num[i]=num[depth]; num[depth]=num[i]; } } private: vector<vector<int> > result; };
47. Permutations II (Recursion, DP)
原文：http://www.cnblogs.com/qionglouyuyu/p/4855305.html