Skip to content

104 — Subsets II

Jump to bottom
rebeloper edited this page Jul 14, 2026 · 4 revisions

104 — Subsets II

LeetCode 90 · Medium. Given an integer array nums that may contain duplicates, return all possible subsets (the power set). The solution set must not contain duplicate subsets — return the answer in any order.

🍽️ Intuition

Chapter 101's Subsets assumed every element was unique, so every distinct choice of indices produced a distinct subset. Duplicates break that assumption: nums = [1, 2, 2] has two 2s at different indices, but choosing "the first 2" versus "the second 2" produces the same subset [1, 2] twice. The fix isn't to generate everything and deduplicate afterward — it's to sort the duplicates next to each other and refuse to start a second identical branch at the same recursion depth.

🚩 Pattern-Recognition Cue

"May contain duplicates" + "must not contain duplicate subsets" is the tell: whenever a problem explicitly calls out duplicate input alongside a requirement for duplicate-free output, that's a signal to sort first and add a same-level skip — the classic "sort + skip adjacent duplicates" move that recurs across this whole category.

🐢 Brute Force

Reuse the bitmask enumeration from Subsets — generate all 2^n index-subsets blindly, without regard for which values are duplicates — then dump every result into a Set to deduplicate after the fact.

func subsetsWithDupBruteForce(_ nums: [Int]) -> [[Int]] {
    let n = nums.count
    var seen: Set<[Int]> = []

    for mask in 0..<(1 << n) {
        var subset: [Int] = []
        for i in 0..<n {
            if mask & (1 << i) != 0 {
                subset.append(nums[i])
            }
        }
        // Sort before inserting: nums isn't sorted, so two index-subsets holding the same values
        // in a different relative order would otherwise dodge the Set dedup entirely.
        seen.insert(subset.sorted())
    }

    return Array(seen)
}

// smoke test
print(subsetsWithDupBruteForce([1, 2, 2]).count)   // 6 (order from Set is unpredictable)
print(subsetsWithDupBruteForce([]))                 // [[]]

Big-O: O(n · 2^n) time to generate every mask, plus O(2^n) hashing/insertion overhead for the Set — every duplicate subset is fully built and hashed before being thrown away, and the result order is unpredictable since Set has none.

🚀 Optimal

Sort nums first so identical values sit next to each other, then skip any candidate that equals its predecessor at the same recursion depth — that's the signal "I already explored this exact branch starting from an identical sibling value."

func subsetsWithDup(_ nums: [Int]) -> [[Int]] {
    let sorted = nums.sorted()
    var results: [[Int]] = []
    var path: [Int] = []

    func backtrack(_ start: Int) {
        results.append(path)

        for i in start..<sorted.count {
            if i > start && sorted[i] == sorted[i - 1] { continue }   // prune: duplicate sibling branch

            path.append(sorted[i])
            backtrack(i + 1)
            path.removeLast()
        }
    }

    backtrack(0)
    return results
}

// smoke test — same cases as the brute force, deterministic order this time
print(subsetsWithDup([1, 2, 2]))   // [[], [1], [1, 2], [1, 2, 2], [2], [2, 2]]
print(subsetsWithDup([]))          // [[]]

Big-O: O(n · 2^n) worst case (same theoretical bound, since with no duplicates every subset is still unique), but each duplicate sibling branch is skipped with an O(1) check before recursing into it — no wasted generation, no hashing, and the output order is deterministic.

🔑 The Key Insight

The i > start condition is the crux: it does not forbid using the value 2 twice in the same subset (that's still allowed and correct — [2, 2] is a valid subset when both 2s exist in the input). It forbids starting a new sibling branch at the same recursion depth with a value identical to one already tried at that depth, because that sibling branch would explore the exact same set of subsets as the one already explored. Sorting is what makes the check O(1): without sorting, the two 2s might not be adjacent, and detecting "have I already tried this value at this level" would require scanning everything tried so far instead of just glancing one index back.

🔗 Related Chapters

  • DFS and Backtracking — the same "record on every node" Subsets template, with one added guard clause for duplicates.
  • Arrays and Strings — sorting nums up front is what turns "are there duplicates anywhere" into "is this one adjacent to a duplicate," an O(1) check instead of an O(n) scan.

🧸 Memory Sentence

Subsets II is Subsets with one extra rule: sort first, and never let a duplicate value start a second branch at the same level it already started one at.

✅ Check Your Understanding

  1. Why does if i > start && sorted[i] == sorted[i - 1] { continue } use i > start rather than i > 0? What would break if it were i > 0 instead?
  2. subsetsWithDup([2, 2]) should return exactly three subsets: [], [2], [2, 2]. Trace the recursion and confirm none of them are produced twice.
  3. The brute force's Set<[Int]> approach gives the mathematically correct set of subsets. Why is it still worth calling "brute force" if its output is exactly right?

⬅️ Previous: Permutations · Next: Combination Sum II ➡️

Clone this wiki locally