medium

Subsets

Return every possible subset of a set of unique numbers.

1. Define the problem

Subsets

Given an integer array nums of unique elements, return all possible subsets (the power set ). The solution set must not contain duplicate subsets. Use backtracking that walks the array once: at each index, record the current path as a subset, then try including each remaining element in turn — recursing forward and undoing the choice afterward so the next element can be tried in its place.

Constraints

  • 1 ≤ nums.length ≤ 10
  • -10 ≤ numsi ≤ 10
  • All the numbers of nums are unique

Example

Inputnums = [1, 2, 3]
Output[[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]

Explanation Every element is either included or excluded, giving 23 = 8 total subsets.

2. Know the words first

In plain terms

Power set
The set of all possible subsets of a set, including the empty subset and the full set itself.
3. Visualize the solution

The row is the path: try each element, record it, undo to try the next

The row is the path: try each element, record it, undo to try the next
Statusrecord

The row is the path being built — nothing is picked yet, so all three slots are blank. Path=[] is recorded as the first subset, the empty one.

What happens in this step

path = []
result so far = [[]]

backtrack(0) is entered: record the current path immediately, before trying any element — this captures the empty subset. nums = [1, 2, 3], so the path can hold at most three picks.
Step 1 of 5

Steps to visualize

  1. The row has one slot per element of nums = [1, 2, 3] — it holds the path being built, with a blank for every slot not yet picked.
  2. Record the current path as a subset the moment you enter a new call — including the empty path.
  3. Starting from the current index, try including the next element and recurse.
  4. After recursing, remove that element from the path (undo) so the next element at this level can be tried instead.
  5. Continue until every starting index has been tried at every depth.
4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

The row is the path: try each element, record it, undo to try the next
Statusrecord

The row is the path being built — nothing is picked yet, so all three slots are blank. Path=[] is recorded as the first subset, the empty one.

What happens in this step

path = []
result so far = [[]]

backtrack(0) is entered: record the current path immediately, before trying any element — this captures the empty subset. nums = [1, 2, 3], so the path can hold at most three picks.
Step 1 of 5
5. Solution

Solution

solution.tsTypeScript
function subsets(nums) {
  const result = [];
  const path = [];

  function backtrack(start) {
    result.push(path.slice());

    for (let i = start; i < nums.length; i++) {
      path.push(nums[i]);
      backtrack(i + 1);
      path.pop();
    }
  }

  backtrack(0);
  return result;
}
Time
O(n · 2^n)
Space
O(n)
6. Test cases

Test cases

InputExpectedCovers
nums = [1, 2, 3][[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]example from the docstring
nums = [5][[], [5]]smallest valid input, a single element
nums = [1, 2][[], [1], [1,2], [2]]two elements, four subsets
nums = [-2, -1][[], [-2], [-2,-1], [-1]]negative values
nums = [1, 2, 3, 4]all 16 subsets of 1, 2, 3, 4larger input, full power set of size 16
nums = [0, 1][[], [0], [0,1], [1]]zero is a valid, falsy-but-included element
nums = [4, 5, 6][[], [4], [4,5], [4,5,6], [4,6], [5], [5,6], [6]]three elements with non-consecutive-looking values

Keep reading