Subsets II

class Solution {
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> out;
        vector<int> path;
        function<void(int)> dfs = [&](int start){
            out.push_back(path);
            for (int i = start; i < (int)nums.size(); ++i) {
                if (i > start && nums[i] == nums[i - 1]) continue;
                path.push_back(nums[i]);
                dfs(i + 1);
                path.pop_back();
            }
        };
        dfs(0);
        return out;
    }
};

import "sort"

func subsetsWithDup(nums []int) [][]int {
    sort.Ints(nums)
    out := [][]int{}
    path := []int{}
    var dfs func(start int)
    dfs = func(start int) {
        cp := make([]int, len(path))
        copy(cp, path)
        out = append(out, cp)
        for i := start; i < len(nums); i++ {
            if i > start && nums[i] == nums[i-1] {
                continue
            }
            path = append(path, nums[i])
            dfs(i + 1)
            path = path[:len(path)-1]
        }
    }
    dfs(0)
    return out
}

from typing import List

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        out: List[List[int]] = []
        path: List[int] = []

        def dfs(start: int) -> None:
            out.append(path[:])
            for i in range(start, len(nums)):
                if i > start and nums[i] == nums[i - 1]:
                    continue
                path.append(nums[i])
                dfs(i + 1)
                path.pop()

        dfs(0)
        return out

function subsetsWithDup(nums) {
    nums.sort((a, b) => a - b);
    const out = [];
    const path = [];
    const dfs = (start) => {
        out.push([...path]);
        for (let i = start; i < nums.length; i++) {
            if (i > start && nums[i] === nums[i - 1]) continue;
            path.push(nums[i]);
            dfs(i + 1);
            path.pop();
        }
    };
    dfs(0);
    return out;
}

class Solution {
    private int[] nums;
    private List<List<Integer>> out = new ArrayList<>();
    private List<Integer> path = new ArrayList<>();

    private void dfs(int start) {
        out.add(new ArrayList<>(path));
        for (int i = start; i < nums.length; i++) {
            if (i > start && nums[i] == nums[i - 1]) continue;
            path.add(nums[i]);
            dfs(i + 1);
            path.remove(path.size() - 1);
        }
    }

    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        this.nums = nums;
        dfs(0);
        return out;
    }
}

function subsetsWithDup(nums: number[]): number[][] {
    nums.sort((a, b) => a - b);
    const out: number[][] = [];
    const path: number[] = [];
    const dfs = (start: number): void => {
        out.push([...path]);
        for (let i = start; i < nums.length; i++) {
            if (i > start && nums[i] === nums[i - 1]) continue;
            path.push(nums[i]);
            dfs(i + 1);
            path.pop();
        }
    };
    dfs(0);
    return out;
}