Start practising

Subsets II

Medium Recursion & Backtracking Pick / Not-Pick Original on LeetCode

Subsets II is a medium recursion & backtracking problem solved with the pick / not-pick pattern. The best approach, optimal (skip equal siblings), runs in O(n · 2ⁿ) time and O(n) space. Below are 2 approaches in Java, from generate all, deduplicate with a set up.

Problem

NoteLearn how to handle duplicates

Given an integer array that may contain duplicates, return all possible subsets without duplicate subsets, in any order.

Examples

Example 1

Input
nums = [1, 2, 2]
Output
[[], [1], [1,2], [1,2,2], [2], [2,2]]

Example 2

Input
nums = [0]
Output
[[], [0]]

Constraints

  • 1 <= nums.length <= 10
  • nums may contain duplicates; the answer must not.

Animated walkthrough

A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.

Concepts first, then the problem and every approach, step by step.

Space to play or pause · ← → to jump a step · click or drag the bar to seek

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the Java code.

ApproachTimeSpace
Generate all, deduplicate with a setO(n · 2ⁿ)O(n · 2ⁿ)
Optimal (skip equal siblings)O(n · 2ⁿ)O(n)

1Generate all, deduplicate with a set

TimeO(n · 2ⁿ)
SpaceO(n · 2ⁿ)

Sort, generate all 2ⁿ subsets with pick / not-pick, and put them in a set of lists.

  1. Sort nums; pick / not-pick recursion; add each subset to a HashSet.
Java
class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        Set<List<Integer>> seen = new HashSet<>();
        build(nums, 0, new ArrayList<>(), seen);
        return new ArrayList<>(seen);
    }

    private void build(int[] nums, int i, List<Integer> path, Set<List<Integer>> seen) {
        if (i == nums.length) { seen.add(new ArrayList<>(path)); return; }
        build(nums, i + 1, path, seen);
        path.add(nums[i]);
        build(nums, i + 1, path, seen);
        path.remove(path.size() - 1);
    }
}

2Optimal (skip equal siblings)

TimeO(n · 2ⁿ)Up to 2ⁿ distinct subsets, each copied in O(n).
SpaceO(n)Recursion depth, not counting the output.

Sort. Every call records the current path, then tries each next element from start. If i > start and nums[i] == nums[i - 1], picking it at this level would repeat a subset already produced by its twin, so skip it. Deeper levels may still use the duplicate.

  1. Record a copy of the path.
  2. For i from start: if i > start && nums[i] == nums[i - 1], continue.
  3. Add nums[i], recurse with i + 1, remove.
Java
class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> out = new ArrayList<>();
        build(nums, 0, new ArrayList<>(), out);
        return out;
    }

    private void build(int[] nums, int start, List<Integer> path, List<List<Integer>> out) {
        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]);
            build(nums, i + 1, path, out);
            path.remove(path.size() - 1);
        }
    }
}

Edge cases to test

  • All elements equal
  • Duplicates that are not adjacent until you sort

Hints

Hint 1

Sort first. When choosing the next element at the same level, skip a value equal to the previous sibling.

FAQ

What is the best time complexity for Subsets II?

Optimal (skip equal siblings) runs in O(n · 2ⁿ) time and O(n) extra space. Up to 2ⁿ distinct subsets, each copied in O(n).

Which pattern does Subsets II use?

It is a recursion & backtracking problem that uses the pick / not-pick pattern. Other problems with the same pattern: Generate all binary strings without consecutive 1's, Subsets (2 choices per element), Combinations.

Is there a brute force solution for Subsets II?

Yes. Generate all, deduplicate with a set takes O(n · 2ⁿ) time and O(n · 2ⁿ) space. Sort, generate all 2ⁿ subsets with pick / not-pick, and put them in a set of lists.

Which edge cases should I test for Subsets II?

All elements equal; Duplicates that are not adjacent until you sort.