47. Permutations II

O(n*n!) time
先写 dfs 版本再写循环版本
先排序，对于每个位置，从小到大枚举之后的每个数（相同的数要跳过）

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        res, n = [], len(nums)
        def dfs(A, b):
            if b == n:
                res.append(A)
                return
            for i in range(b, n):
                if i > b and A[i] == A[b]:
                    continue
                A[b], A[i] = A[i], A[b]
                dfs(A[:], b + 1)
        dfs(nums, 0)
        return res

class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        sort(begin(nums), end(nums));
        dfs(nums, 0);
        return res;
    }

    void dfs(vector<int> nums, int b) { // 注意nums是深拷贝
        int n = nums.size();
        if (b == n) {
            res.push_back(nums);
        }
        for (int i = b; i < n; ++i) {
            if (i > b && nums[i] == nums[b]) continue; // 去重
            swap(nums[i], nums[b]);
            dfs(nums, b + 1);
        }
    }

    vector<vector<int>> res;
};

O(n*n!) time

class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> res;
        do {
            res.push_back(nums);
        } while (next(nums));
        return res;
    }

    bool next(vector<int> &A) {
        int n = A.size();
        int x = 0, y = 0;
        for (int i = n - 1; i > 0; --i) {
            if (A[i - 1] < A[i]) {
                x = i - 1;
                y = i;
                break;
            }
        }
        if (y == 0) return false;
        for (int i = n - 1; i > x; --i) {
            if (A[i] > A[x]) {
                swap(A[i], A[x]);
                break;
            }
        }
        reverse(A.begin() + y, A.end());
        return true;
    }
};

O(nⁿ) time

class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        n = nums.size();
        visited.resize(n);
        sort(begin(nums), end(nums));
        dfs(nums);
        return res;
    }

    void dfs(const vector<int> &nums) {
        if (v.size() == n) {
            res.push_back(v);
            return;
        }
        for (int i = 0; i < n; ++i) {
            if (visited[i] || i > 0 && nums[i] == nums[i - 1] && !visited[i - 1]) continue; // 如果前一个数已经访问过（还没被访问）并且跟这个数相同，则再访问这个数是重复的，如果前一个数正在被访问（说明在v里）则可以访问当前这个数，即便跟前一个数相同
            visited[i] = true;
            v.push_back(nums[i]);
            dfs(nums);
            v.pop_back();
            visited[i] = false;
        }
    }

    int n;
    vector<bool> visited;
    vector<int> v;
    vector<vector<int>> res;
};