[LC] 0090 Subsets II

Java

import java.util.*;

/**
 * <a href="https://leetcode.cn/problems/subsets-ii/">Subsets II</a>
 * 位运算；数组；回溯
 */
class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        dfs(false, 0, nums, new ArrayList<>(), res);
        return res;
    }

    private void dfs(boolean choosePre, int cur, int[] nums, List<Integer> path, List<List<Integer>> res) {
        if (cur == nums.length) {
            res.add(new ArrayList<>(path));
            return;
        }
        dfs(false, cur + 1, nums, path, res);
        if (!choosePre && cur > 0 && nums[cur] == nums[cur - 1]) {
            return;
        }
        path.add(nums[cur]);
        dfs(true, cur + 1, nums, path, res);
        path.remove(path.size() - 1);
    }
}

Go

import "sort"

func subsetsWithDup(nums []int) (res [][]int) {
    sort.Ints(nums)
    var dfs func(bool, int, []int)
    dfs = func(choosePre bool, cur int, path []int) {
        if cur == len(nums) {
            res = append(res, append([]int{}, path...))
            return
        }
        dfs(false, cur+1, path)
        if !choosePre && cur > 0 && nums[cur] == nums[cur-1] {
            return
        }
        path = append(path, nums[cur])
        dfs(true, cur+1, path)
        path = path[:len(path)-1]
    }
    dfs(false, 0, []int{})
    return
}

JavaScript

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var subsetsWithDup = function (nums) {
    nums.sort((a, b) => a - b);
    let res = [];
    const dfs = (choosePre, cur, nums, path) => {
        if (cur === nums.length) {
            res.push(path.slice());
            return;
        }
        dfs(false, cur + 1, nums, path);
        if (!choosePre && cur > 0 && nums[cur - 1] === nums[cur]) {
            return;
        }
        path.push(nums[cur]);
        dfs(true, cur + 1, nums, path);
        path.pop();
    };
    dfs(false, 0, nums, []);
    return res;
};

PHP

class Solution {

    /**
     * @param Integer[] $nums
     * @return Integer[][]
     */
    function subsetsWithDup(array $nums): array {
        sort($nums);
        $res = [];
        $this->dfs(false, 0, $nums, [], $res);
        return $res;
    }

    private function dfs($choose_pre, $cur, $nums, $path, &$res): void {
        if ($cur == count($nums)) {
            $res[] = $path;
            return;
        }
        $this->dfs(false, $cur + 1, $nums, $path, $res);
        if (!$choose_pre && $cur > 0 && $nums[$cur] == $nums[$cur - 1]) {
            return;
        }
        $path[] = $nums[$cur];
        $this->dfs(true, $cur + 1, $nums, $path, $res);
        array_pop($path);
    }
}