Pattern this teaches:Backtracking Basics
Subsets II
A medium Backtracking interview guide. Task statement, worked examples, intuition, and step-by-step solutions.
- Topic
- Backtracking
- Sheets
- 2
- Core for
- 0 roles
The problem
The array may contain repeated values. Return every distinct subset you can form from it, each exactly once, in any order; two subsets that contain the same values count as the same subset.
Example 1
- Input
- nums = [3,1,3]
- Output
- [[],[1],[3],[1,3],[3,3],[1,3,3]]
- Why
- The duplicate 3 would produce repeated subsets; each distinct one is kept once.
Example 2
- Input
- nums = [0]
- Output
- [[], [0]]
- Why
- A single-element array has exactly two unique subsets.
Constraints
- 1 <= nums.length <= 10
- -10 <= nums[i] <= 10
How to think about it
Updated 2026-09-29Duplicate values become identical branches only when chosen at the same decision depth. Sorting the array clusters equal numbers together, turning duplicate prevention into a local rule: inside the same loop iteration, never begin an exploratory branch with an element identical to the one just inspected and discarded.
Approaches, worst first
Power set with hash set filtering
time O(n * 2^n) · space O(n * 2^n)
Sort each generated subset and insert it into a hash table to discard duplicates. Correct but wasteful, as it generates the full 2^n search tree and serializes every subset even when almost all branches are redundant.
Sort and skip identical siblingsWrite this one
time O(n * 2^n) · space O(n)
Sort first. In the recursive loop from startIndex to n, if i > startIndex and nums[i] == nums[i - 1], skip nums[i]. Identical values can still be picked sequentially in deeper levels, but siblings at the same depth never branch on identical values.
Where people lose marks · 3
- Skipping duplicates without sorting the array first. If identical values are scattered, adjacent equality checks fail and duplicate subsets escape into the result.
- Using i > 0 instead of i > startIndex in the skip check. That mistakenly forbids picking legitimate duplicate elements across consecutive recursion depths, such as [2, 2].
- Modifying or sorting the original array when immutability is expected, rather than sorting a cloned copy.
The theory behind it
Backtracking — the ground this problem stands on. All Backtracking problems
What Backtracking is
Backtracking is an organized trial-and-error search through a maze of possibilities. You make a tentative choice, move forward to explore where that path leads, and if you hit a dead end or finish finding an answer, you back up and undo that choice. By cleaning up your changes before trying the next option, a single shared board or list is explored thoroughly without needing to clone full copies of your data at every turn.
When to reach for it
Reach for backtracking when a problem asks to generate all possible solutions, like all subsets, permutations, valid parentheses combinations, or word search paths on a board. Signals include puzzles with strict constraint rules, like placing eight non-attacking queens on a chessboard or solving a Sudoku grid. Whenever you must construct combinations step by step and abandon dead-end branches early before wasting time exploring impossible paths, use backtracking.
How the pattern works
Follow a three-step rhythm inside a loop: choose, explore, and unchoose. First, check if the current state satisfies your goal; if so, save a copy of it and return. Next, prune illegal moves immediately using constraint checks so unpromising branches are skipped. For each valid candidate, apply the move to your shared path or board, call the recursive function to explore deeper, and finally undo the move right after the call returns. Undoing restores the shared state so sibling choices start from a clean slate.
More Backtracking problems
Track in your role's order
Pick your target role and all 370 problems resequence to what that interview actually asks.
Start freeProblem set and role mapping as of .