Subsets II

PracticeNeetCode ↗LeetCode ↗

Given an integer array nums that may contain duplicates, return all possible subsets, with no duplicate subsets in the result.

Example

Key Pointers

• Sort first so duplicate values sit next to each other — that's what makes duplicate-skipping possible.
• At each recursion level, skip a candidate if it equals the previous candidate and the previous one was already considered at this same level — the standard "skip same-level duplicates" rule.
• The skip check is i > start and nums[i] == nums[i - 1], applied only within the current loop, not across recursion depths.

Step-by-Step Analysis

1. Sort nums.
2. Define backtrack(start): append a copy of path to the result immediately — every partial path is a valid subset.
3. Loop i from start to len(nums): if i > start and nums[i] == nums[i - 1], skip it to avoid a duplicate subset.
4. Otherwise append nums[i], recurse with backtrack(i + 1), then pop.
5. Call backtrack(0) and return the result.

Complexity

Time: O(n · 2ⁿ) — Space: O(n) recursion depth

Code

def subsetsWithDup(nums: list[int]) -> list[list[int]]:
    nums.sort()
    result = []
    path = []

    def backtrack(start: int) -> None:
        result.append(path[:])
        for i in range(start, len(nums)):
            if i > start and nums[i] == nums[i - 1]:
                continue
            path.append(nums[i])
            backtrack(i + 1)
            path.pop()

    backtrack(0)
    return result

Code Explanation

How the solution above works, piece by piece.

1. Sort first so duplicates are adjacent.
2. Like Subsets, every call records path.
3. if i > start and nums[i] == nums[i - 1]: continue: at the same depth, skip a value equal to the previous one; it would start an identical branch.
4. i > start (not i > 0) matters: the first copy at each level is allowed, so [2, 2] can still be formed by going deeper.
5. O(n · 2ⁿ) in the worst case (all distinct).

Visual Walkthrough

The recursion tree for nums = [1, 2, 2]:

Video Explanation

NeetCode — Subsets II, LeetCode 90