Subsets II (LeetCode 90)

The problem

You get a list of integers that may contain duplicates. Return every possible subset, but each distinct subset only once. [1,2] built from the first 2 and [1,2] built from the second 2 count as the same subset.

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

Plain Subsets would give 8 lists, with [2] and [1,2] each appearing twice. Only 6 are distinct.

How to think about it

Start with brute force. Run the normal Subsets backtracking, convert each subset to a sorted tuple, and throw them into a set. It works, but you still build all 2ⁿ subsets, you pay for sorting and hashing each one, and the interviewer will ask you to avoid the duplicates in the first place.

Where do duplicates come from? Sort the input so equal values sit next to each other: [1, 2, 2]. At the root, the loop tries “start with the first 2” and later “start with the second 2”. Both branches then explore exactly the same remaining options, so they produce exactly the same subsets. The duplicate isn’t in going deeper with a second 2 (that gives [2,2], which is new). It’s in choosing the same value twice at the same position in the subset.

The key insight: at one level of the tree, use each value only once. Inside a single call’s loop, every iteration decides “what’s the next element of the subset”. If nums[i] == nums[i-1] and i > start, this value was already tried as the next element in this same loop, so skip it. The i > start part is what still lets you pick the second 2 after the first one, in a deeper call.

Which pattern is this? Backtracking with a de-duplication rule. The tell is “the input may contain duplicates, but the answer must not”. Sort first, then skip at the same level: this exact trick comes back in Combination Sum II.

Approach

1. Sort nums so duplicates are adjacent.
2. bt(start, path) records a copy of path (every node is a subset).
3. Loop i from start to the end. If i > start and nums[i] == nums[i-1], skip: that value was already the next choice at this level.
4. Otherwise choose nums[i], recurse with i + 1, and pop it.
5. Start with bt(0, []).

Solution

def subsets_with_dup(nums):
    nums.sort(); res = []                    # sort so equal values are adjacent
    def bt(start, path):
        res.append(path[:])
        for i in range(start, len(nums)):
            if i > start and nums[i] == nums[i-1]: continue   # same value, same level: skip
            path.append(nums[i]); bt(i + 1, path); path.pop()
    bt(0, []); return res
# subsets_with_dup([1,2,2]) -> [[],[1],[2],[1,2],[2,2],[1,2,2]]

The function returns the subsets in tree order: [[], [1], [1,2], [1,2,2], [2], [2,2]]. The comment lists the same six in a different order, which is fine since order doesn’t matter.

Dry run

On nums = [1, 2, 2] (already sorted):

Two branches are skipped, and six unique subsets come out.

Complexity

• Time: O(n·2ⁿ). In the worst case (all values distinct) the tree has 2ⁿ nodes and each copy costs O(n). The sort adds O(n log n), which is smaller.
• Space: O(n) extra for the recursion and path, not counting the output.

Edge cases and pitfalls

• Forgetting to sort. The skip rule only works if equal values are adjacent. [2, 1, 2] unsorted gives duplicates.
• Using i > 0 instead of i > start. That skips the second 2 even in deeper calls, so [2,2] and [1,2,2] go missing.
• All the same value, e.g. [2,2,2], gives [[], [2], [2,2], [2,2,2]]: four subsets, one per count.
• Empty input returns [[]].
• Note the code sorts nums in place. Copy it first if the caller needs the original order.

Related problems

• Subsets (LeetCode 78): the same tree without duplicates to worry about.
• Combination Sum II (LeetCode 40): the same skip rule, plus a target sum.
• Permutations II (LeetCode 47): de-duplication for orderings, which needs a different rule.