mediumBacktracking

Subsets II

Generate all distinct subsets of an array that may contain duplicate values. Sort each subset and print subsets lexicographically, empty first.

LeetCode ↗

Work through the cases

3 examples

Input notation

Integers separated by spaces; at most 12 values.

Expected result

One bracketed comma-separated subset per line, without spaces.

Case 1

Input

1 1

Expected output

[]
[1]
[1,1]

Case 2

Input

2 3

Expected output

[]
[2]
[2,3]
[3]

Case 3

Input

0 0 0

Expected output

[]
[0]
[0,0]
[0,0,0]

These notes use simplified input/output notation. The linked platform defines the method signature and judge format.

FROM IDEA TO IMPLEMENTATION

Understand the approach.

Compare the documented approaches below. Brute force, better, and optimal versions appear where available; a direct exercise may need only one approach.

The first idea is the same DFS as Subsets: take or skip each index. Correct, but duplicates make [1, 2] appear twice. n ≤ 10 is small, yet the solution set must be unique. The bottleneck is treating equal values at different indices as distinct choices. Sort so equals sit together; skip the same value on the “not take” branch so each multiset is generated once. After sorting, DFS: take i, then on the skip path jump over every later equal nums[i]. How many copies we take is decided by recursion depth, never as two identical subsets side by side.

We can first sort the array nums to facilitate deduplication.

Then, we design a function dfs(i), which represents the current search for subsets starting from the i-th element. The execution logic of the function dfs(i) is as follows:

If i ≥ n, it means all elements have been searched, add the current subset to the answer array, and end the recursion.

If i < n, add the i-th element to the subset, execute dfs(i + 1), then remove the i-th element from the subset. Next, we check if the i-th element is the same as the next element. If they are the same, skip the element in a loop until we find the first element different from the i-th element, then execute dfs(i + 1).

Finally, we only need to call dfs(0) and return the answer array.

The time complexity is O(n × 2^n), and the space complexity is O(n). Here, n is the length of the array nums.

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

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

    private void dfs(int i) {
        if (i >= nums.length) {
            ans.add(new ArrayList<>(t));
            return;
        }
        t.add(nums[i]);
        dfs(i + 1);
        int x = t.remove(t.size() - 1);
        while (i + 1 < nums.length && nums[i + 1] == x) {
            ++i;
        }
        dfs(i + 1);
    }
}

Reference code. Platform solutions may use supplied node types, imports, or collection libraries; foundational examples are complete programs.

Solutions adapted from Doocs / LeetCode contributors, licensed under CC BY-SA 4.0. Formatting changed; TypeScript versions converted to JavaScript. Supplemental implementations and approach notes added. Adapted solution material is available under the same license.