Subsets II — Solution

Problem

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

• Input: nums = [1,2,2]
• Output: [[], [1], [1,2], [1,2,2], [2], [2,2]]
• Explanation: All six unique subsets — the two 2s together form [2,2] as a distinct subset.

Counter-example: without deduplication, the two copies of 2 would each independently produce [2] and [1,2], leaving those subsets duplicated in the output.

Intuition

This is the standard power set problem with one wrinkle: equal values chosen at the same decision point produce identical subtrees, so we'd generate duplicate subsets. The fix is to sort the input so duplicates are adjacent, then skip any value at the same recursion level that equals the one we just tried — that entire branch would mirror work we already did.

Solution — Sort + Backtrack with Skip

Sort the input so equal values sit next to each other, then run backtracking. At every call, record the current subset. Then for each remaining index, skip it if its value equals the previous index's value at the same level (same start), otherwise extend and recurse.

1. Sort nums so all duplicate values are adjacent.
2. Initialize a result list and an empty current-subset.
3. Call backtrack(start=0): record the current subset as a new result entry.
4. For each index i from start to the end of the array:
   • If i > start and nums[i] == nums[i-1], skip — that value was already the root of an identical branch at this level.
   • Otherwise, append nums[i], recurse with start = i+1, then pop (backtrack).

1def subsetsWithDup(self, nums: list[int]) -> list[list[int]]:
2    nums.sort()  # duplicates must be adjacent for the skip logic to work
3    result = []
4
5    def backtrack(start: int, current_subset: list[int]) -> None:
6        result.append(current_subset[:])  # snapshot before extending
7
8        for i in range(start, len(nums)):
9            if i > start and nums[i] == nums[i - 1]:
10                continue  # same value at this level already explored in prior iteration
11            current_subset.append(nums[i])
12            backtrack(i + 1, current_subset)
13            current_subset.pop()  # undo to try the next element
14
15    backtrack(0, [])
16    return result

Time: O(n · 2^n) — at most 2^n unique subsets exist, and copying each one takes O(n).
Space: O(n · 2^n) — storing all subsets; the recursion stack itself is only O(n) deep.

Complexity Summary

Common Mistakes

• Forgetting to sort. The condition nums[i] == nums[i-1] only catches duplicates if they're adjacent. Without sorting, non-adjacent equal values slip through and produce duplicate subsets.
• Using i > 0 instead of i > start. Checking i > 0 wrongly skips a value the very first time it appears at a given recursion level — for example, [2] and [1,2] would both be missing from the output. The guard must compare i against the current call's start, not zero.
• Appending the list without copying. In Python, result.append(current_subset) stores a reference that mutates as backtracking continues, leaving every recorded entry empty at the end. Always snapshot with current_subset[:].
• Passing i instead of i+1 when recurring. Using i as the next start lets the same index be chosen again, producing subsets where an element appears more times than it exists in nums.
• Confusing the add-to-result placement with combination problems. Unlike problems that collect subsets only at a certain size or sum, here every intermediate state is a valid result, so the result.append must sit unconditionally at the top of the function — not only when the loop finishes.

Related Problems

• subsets — the same backtracking skeleton without any duplicates; understand this first before adding the skip logic
• combination-sum-ii — identical sort + skip-duplicate pattern, but only collects paths that reach a target sum
• permutations — backtracking for ordered arrangements rather than unordered selections
• palindrome-partitioning — backtracking that enumerates all ways to split a string, structurally similar recursion
• combinations — choose exactly k elements from 1..n with no input duplicates; closely related subset-selection structure