How do you approach Subsets II?

Sort first so duplicates are adjacent.

What are common mistakes on Subsets II?

Pushing the working array into the results without copying it, so every entry aliases the same array. Forgetting to undo the choice after the recursive call returns. Deduplicating at the end instead of pruning at the branch - the difference between passing and timing out.

gitGood.dev

← Back to problems

Subsets II

MediumAlgorithms

Description

Given an integer array `nums` that may contain duplicates, return all possible **unique** subsets (the power set). The result must not contain duplicate subsets. Each subset is returned in non-decreasing order, and the list of subsets is ordered with each subset's elements ascending and subsets compared lexicographically.

Example 1

Input: nums = [1,2,2]

Output: [[],[1],[1,2],[1,2,2],[2],[2,2]]

Explanation: Duplicates collapsed; subsets sorted.

Constraints

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

Subsets II: approach, complexity and pitfalls

A medium backtracking problem, graded against 3 test cases (1 of them hidden).

The pattern: Backtracking

Systematic exploration of all candidates, abandoning partial ones that cannot work.

Reach for it when you see: "All permutations/combinations/subsets", or constraint puzzles like N-Queens and Sudoku.

More Backtrackingproblems →

If you are stuck

Show the 2-step hint ladder

Sort first so duplicates are adjacent.
At each recursion level, skip a value equal to the previous sibling already tried.

The optimal approach

Show the approach: The approach

Backtracking with duplicate skipping. Sort `nums`. At each `start` index, iterate; if the current value equals the previous one at the same level (`i > start && nums[i] === nums[i-1]`), skip it to avoid duplicate subsets. Record the path at every node.

Time: O(n·2ⁿ). Space: O(n) recursion.

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.
Duplicate values. Repeated values appear in the input, so any logic that assumes distinct elements - or that skips over equal neighbours - is exercised.
Zero. Zero appears in the input, which is the value most likely to break a truthiness check used in place of an explicit comparison.

Common Backtracking mistakes

These apply to the pattern as a whole, not just this problem.

Pushing the working array into the results without copying it, so every entry aliases the same array.
Forgetting to undo the choice after the recursive call returns.
Deduplicating at the end instead of pruning at the branch - the difference between passing and timing out.