Skip to main content

90. Subsets II

medium

Generate the power set when the input may contain duplicates and the output must have no duplicate subsets. The first problem that forces you to think carefully about how to prune duplicate branches in a recursion tree.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

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 solution in any order.

Constraints

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

Examples

Example 1

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

Example 2

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

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Sort first — duplicates must be adjacent for the next idea to work.

Hint 2

When you're iterating at depth d to pick the next element, skip values equal to the previous value in this iteration (but the first time at this depth is fine).

Hint 3

The rule: at iteration index j > start, if nums[j] == nums[j-1], skip. This prunes [1,2a] vs [1,2b] from producing the same subset twice.

Hint 4

Same skeleton as Subsets — only the dedup line + the initial sort are new.

Solution approach

Reveal approach

Sort nums in place. Run the same backtracking template as Subsets — snapshot the path on entry, loop j from start, include, recurse, pop. The single new line: at iteration index j > start, skip if nums[j] == nums[j-1]. This dedup rule is subtle: 'j > start' (not 'j > 0') means the very first time you consider this index at this depth is always allowed, but a second branch at the same depth that picks the same value gets pruned. Time is O(n * 2^n) worst case (same as Subsets when there are no duplicates); space is O(n) recursion stack.

Complexity

Time
O(n * 2^n)
Space
O(n)

Related patterns

  • backtracking
  • recursion
  • duplicates-handling

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Meta
  • Bloomberg
  • Microsoft

Practice these live with InterviewChamp.AI

Drill Subsets II and Recursion problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →