Subsets II

MEDIUM✓ CHIP-TIMEDLC #90 — FULL STATEMENT ↗

The drill: Same as generating every possible group from an array, except the array can repeat values — return every distinct group exactly once, with no duplicate group appearing twice just because a value repeats.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

An array that may hold duplicate values arrives, and the goal is the same as ordinary subset generation: list every group that can be pulled from it, empty group and full array included.

The twist is that repeated values must not create repeated groups — if two elements share a value, choosing one versus the other can silently produce the same-looking subset twice, and only one copy should survive.

Two subsets count as identical when they hold the same values the same number of times, regardless of which physical positions supplied them.

EX 01

nums = [1, 1]

→ [[], [1], [1, 1]]

MINIMUM DUPLICATE PAIR

EX 02

nums = [4, 4, 4]

→ [[], [4], [4, 4], [4, 4, 4]]

TRIPLE DUPLICATE

EX 03

nums = [1, 2, 2]

→ [[], [1], [1, 2], [1, 2, 2], [2], [2, 2]]

arrays are short, generally well under twenty elements
values may repeat any number of times
each distinct subset, by value rather than by position, appears exactly once
the empty subset and the full array both belong in the output

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

Duplicate values mean two different index choices can build the identical group — the fix isn't in what you output, it's in which branches the recursion is allowed to take.

HINT 2 THE STRUCTURE

Sort the array so equal values sit next to each other. At a given recursion depth, trying a repeated value as anything but the FIRST option there just rebuilds a group you already emitted.

HINT 3 ONE STEP FROM THE ANSWER

Backtrack with a start index like plain Subsets, but at each depth skip nums[i] when i isn't the first index tried at this depth AND nums[i] equals nums[i − 1] — that one guard removes every duplicate.

COACH'S BOARD — THE PATTERN, STEP BY STEP

THE SAME-DEPTH TWIN SKIPPATTERN · SORTED BACKTRACK, SKIP TWINSnums = [1, 2, 2]

STEP 1

Sorted nums: 1, 2, 2. Every recursive call records its own current path as a subset first — then loops over what to add next.

STEP 1 / 9 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/subsets-ii.py — RACE PACE

LANG ▸

PACE ▸

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

        def backtrack(start):
            res.append(list(path))
            for i in range(start, len(nums)):
                if i > start and nums[i] == nums[i - 1]:
                    continue  # same value already tried at this depth
                path.append(nums[i])
                backtrack(i + 1)
                path.pop()

        backtrack(0)
        return res

TIME O(N·2ⁿ)SPACE O(N)PYTHON · RACE PACE · 17 LN

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        found = set()
        for mask in range(1 << n):
            combo = [nums[i] for i in range(n) if mask & (1 << i)]
            found.add(tuple(sorted(combo)))
        return [list(t) for t in found]

TIME O(N·2ⁿ)SPACE O(N·2ⁿ)PYTHON · TRAINING PACE · 8 LN

class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        backtrack(nums, 0, new ArrayList<>(), res);
        return res;
    }

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

TIME O(N·2ⁿ)SPACE O(N)JAVA · RACE PACE · 20 LN

class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        int n = nums.length;
        Set<List<Integer>> found = new HashSet<>();
        for (int mask = 0; mask < (1 << n); mask++) {
            List<Integer> combo = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                if ((mask & (1 << i)) != 0) {
                    combo.add(nums[i]);
                }
            }
            Collections.sort(combo);
            found.add(combo);
        }
        return new ArrayList<>(found);
    }
}

TIME O(N·2ⁿ)SPACE O(N·2ⁿ)JAVA · TRAINING PACE · 17 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED