LeetCode Permutations II

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;
    }
};