Permutations II

class Solution {
    vector<vector<int>> ans;
    vector<int> cur, used;
    vector<int> nums;
    void dfs() {
        if (cur.size() == nums.size()) { ans.push_back(cur); return; }
        for (int i = 0; i < (int)nums.size(); ++i) {
            if (used[i]) continue;
            if (i > 0 && nums[i] == nums[i-1] && !used[i-1]) continue;
            used[i] = 1;
            cur.push_back(nums[i]);
            dfs();
            cur.pop_back();
            used[i] = 0;
        }
    }
public:
    vector<vector<int>> permuteUnique(vector<int>& nums_) {
        nums = nums_;
        sort(nums.begin(), nums.end());
        used.assign(nums.size(), 0);
        dfs();
        return ans;
    }
};

func permuteUnique(nums []int) [][]int {
    sort.Ints(nums)
    n := len(nums)
    used := make([]bool, n)
    cur := []int{}
    ans := [][]int{}
    var dfs func()
    dfs = func() {
        if len(cur) == n {
            tmp := make([]int, n)
            copy(tmp, cur)
            ans = append(ans, tmp)
            return
        }
        for i := 0; i < n; i++ {
            if used[i] {
                continue
            }
            if i > 0 && nums[i] == nums[i-1] && !used[i-1] {
                continue
            }
            used[i] = true
            cur = append(cur, nums[i])
            dfs()
            cur = cur[:len(cur)-1]
            used[i] = false
        }
    }
    dfs()
    return ans
}

from typing import List

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        n = len(nums)
        used = [False] * n
        cur: List[int] = []
        ans: List[List[int]] = []

        def dfs() -> None:
            if len(cur) == n:
                ans.append(cur[:])
                return
            for i in range(n):
                if used[i]:
                    continue
                if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:
                    continue
                used[i] = True
                cur.append(nums[i])
                dfs()
                cur.pop()
                used[i] = False

        dfs()
        return ans

function permuteUnique(nums) {
    nums.sort((a, b) => a - b);
    const n = nums.length;
    const used = new Array(n).fill(false);
    const cur = [];
    const ans = [];
    const dfs = () => {
        if (cur.length === n) {
            ans.push(cur.slice());
            return;
        }
        for (let i = 0; i < n; i++) {
            if (used[i]) continue;
            if (i > 0 && nums[i] === nums[i - 1] && !used[i - 1]) continue;
            used[i] = true;
            cur.push(nums[i]);
            dfs();
            cur.pop();
            used[i] = false;
        }
    };
    dfs();
    return ans;
}

class Solution {
    private int[] nums;
    private boolean[] used;
    private List<Integer> cur = new ArrayList<>();
    private List<List<Integer>> ans = new ArrayList<>();

    public List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums);
        this.nums = nums;
        this.used = new boolean[nums.length];
        dfs();
        return ans;
    }

    private void dfs() {
        if (cur.size() == nums.length) {
            ans.add(new ArrayList<>(cur));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (used[i]) continue;
            if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue;
            used[i] = true;
            cur.add(nums[i]);
            dfs();
            cur.remove(cur.size() - 1);
            used[i] = false;
        }
    }
}

function permuteUnique(nums: number[]): number[][] {
    nums.sort((a, b) => a - b);
    const n = nums.length;
    const used: boolean[] = new Array(n).fill(false);
    const cur: number[] = [];
    const ans: number[][] = [];
    const dfs = (): void => {
        if (cur.length === n) {
            ans.push(cur.slice());
            return;
        }
        for (let i = 0; i < n; i++) {
            if (used[i]) continue;
            if (i > 0 && nums[i] === nums[i - 1] && !used[i - 1]) continue;
            used[i] = true;
            cur.push(nums[i]);
            dfs();
            cur.pop();
            used[i] = false;
        }
    };
    dfs();
    return ans;
}