Subsets II — Backtracking with Duplicate Skip [LC 90]

Problem Statement#

Given an integer array nums that may contain duplicates, return all possible subsets (the power set). The solution set must not contain duplicate subsets and may be returned in any order.

Constraints:

• 1 <= nums.length <= 10
• -10 <= nums[i] <= 10

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

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

Why This Problem Matters#

LeetCode 90 extends Subsets (LC 78) with duplicates — one of the most important backtracking variants. Amazon, Apple, and Google use it to test whether candidates can apply a clean duplicate-skipping rule in recursive exploration.

The same "sort + skip duplicate at same depth" rule appears in Combination Sum II (LC 40), Permutations II (LC 47), and Palindrome Partitioning (LC 131). Learning it once here means you can apply it immediately across an entire family of backtracking problems.

The Core Insight#

Sort first. After sorting, all duplicates are adjacent. Then in backtracking:

• Include the current element and recurse
• Skip all subsequent elements at the same recursion depth that are equal to the current element (they would produce duplicate subsets)

Why does this work? The first occurrence of a duplicate at each depth is included in the recursion. Subsequent occurrences at the same depth would generate identical subsets to what was already explored. By skipping them (but still recursing on them when chosen as the first element at a deeper level), we generate each unique subset exactly once.

The key condition: if i > start and nums[i] == nums[i-1]: skip — only skip if we are not at the first choice for this depth level.

Visual Dry Run#

nums = [1, 2, 2] (sorted)

[]
├── [1]
│   ├── [1,2]
│   │   └── [1,2,2]
│   └── [1,2] ← skip (same as [1,2] already explored at this level)
├── [2]
│   └── [2,2]
└── [2] ← skip (same as [2] already explored at this level)

Result: [[], [1], [1,2], [1,2,2], [2], [2,2]]

Solution (Optimal)#

class Solution:
    def subsetsWithDup(self, nums):
        nums.sort()
        result = []
        def backtrack(start, current):
            result.append(current[:])
            for i in range(start, len(nums)):
                if i > start and nums[i] == nums[i - 1]:
                    continue   # skip duplicate at same depth
                current.append(nums[i])
                backtrack(i + 1, current)
                current.pop()
        backtrack(0, [])
        return result

var subsetsWithDup = function(nums) {
    nums.sort((a, b) => a - b);
    const result = [];
    function backtrack(start, current) {
        result.push([...current]);
        for (let i = start; i < nums.length; i++) {
            if (i > start && nums[i] === nums[i - 1]) continue;
            current.push(nums[i]);
            backtrack(i + 1, current);
            current.pop();
        }
    }
    backtrack(0, []);
    return result;
};

Time: O(2^n) — at most 2^n subsets, each takes O(n) to copy Space: O(n) — recursion depth is at most n

Common Mistakes#

• Not sorting before backtracking — duplicates must be adjacent for the skip condition to work
• Using i > 0 instead of i > start — this would skip duplicate elements even when they are the first choice at a depth level, missing valid subsets
• Forgetting to add the current subset at the beginning of backtrack — each state (before choosing any more elements) is itself a valid subset
• Using a set to deduplicate results — works but is O(2^n * n) space and misses the point; the in-place skip is the intended approach
• Not popping after recursion — the backtracking undo step is essential for correct state management

Interview Tips#

• State the two-step approach: "sort to group duplicates, then skip at same depth"
• Emphasize i > start not i > 0 — this is the most common mistake and shows deep understanding
• Draw the recursion tree for [1,2,2] to show exactly which branches are pruned
• Compare with LC 78 (Subsets without duplicates) — the only addition is the single skip line
• Mention this exact skip condition also solves Combination Sum II (LC 40) and Permutations II (LC 47)

Follow-up Questions#

• How does this differ from Subsets I (LC 78)? (Only difference: one continue line for duplicate skipping)
• How would you use this to solve Combination Sum II (LC 40)? (Same pattern: sort + skip, but stop adding when sum exceeds target)
• What if you want combinations of a specific size k? (Add a length check before appending to result)
• Can you solve this iteratively without recursion? (Yes — start with [[]], for each number add it to existing subsets (skip if it creates a duplicate using the sorted order))
• What is the maximum number of unique subsets for n elements with d duplicates? (Between 2^(n-d) and 2^n depending on duplicate distribution)

Key Takeaways#

• LeetCode 90 is asked at Amazon, Apple, and Google — the canonical "backtracking with duplicates" problem
• Sort the array first: adjacent duplicates enable the O(1) per-step duplicate check
• Skip condition: if i > start and nums[i] == nums[i-1]: continue — only skip non-first choices at each depth
• The i > start (not i > 0) is the critical distinction — it allows the same value as the first choice at a new depth
• Time O(2^n) to generate subsets, O(n) space for recursion stack
• This exact duplicate-skip pattern solves Combination Sum II (LC 40) and Permutations II (LC 47) — learn once, apply everywhere
• Add the current state to results at the start of backtrack — every recursive call represents a valid subset