LeetCode 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].

思路：dfs，但是要注意一点的是如果去重：排序后，可以为每个数都设置一个vis表示是否访问过，当两个相邻的数一样且前一个被访问过了，那么这个数才能使用，才能避免重复。

class Solution {
public:
    int vis[110], a[110];
    vector
  
    > ans;

    void dfs(int cur, int n, vector
   
     &num) { if (cur == n) { vector
    
      tmp; for (int i = 0; i < n; i++) tmp.push_back(a[i]); ans.push_back(tmp); return; } for (int i = 0; i < n; i++) if (!vis[i]) { if (i != 0 && num[i] == num[i-1] && vis[i-1]) continue; vis[i] = 1; a[cur] = num[i]; dfs(cur+1, n, num); vis[i] = 0; } } vector
     
       > permuteUnique(vector
      
        &num) { sort(num.begin(), num.end()); ans.clear(); memset(vis, 0, sizeof(vis)); dfs(0, num.size(), num); return ans; } };