Subsets

BACKTRACKING · MEDIUM

The problem

Given an array of unique integers nums, return all possible subsets (the power set). The solution set must not contain duplicate subsets — return them in any order.

Solution 1: Brute force — bitmask enumeration

Every integer from 0 to 2^n − 1, read in binary, is a unique combination of n bits — treat bit i as “include nums[i]” and enumerate every mask.

Brute force: every integer 0..2^n-1 IS a subset, in binary
    ↓
mask = 0 .. 2^n-1  →  read each bit of mask  →  build the subset
(every possible        (bit i set =             (no recursion needed)
 bit pattern)          include nums[i])

Cost: O(n × 2^n) — same asymptotic class as the backtracking version below.

Interactive visualization

nums = [1, 2] — enumerate every mask from 0 to 2^2−1, read each bit pattern as a subset

Press Play or Step to begin.

Step 0 / 0

The code

function subsetsBrute(nums) {
  const n = nums.length, result = [];
  for (let mask = 0; mask < (1 << n); mask++) {
    const subset = [];
    for (let i = 0; i < n; i++) if (mask & (1 << i)) subset.push(nums[i]);
    result.push(subset);
  }
  return result;
}

Line by line:

mask counts through every integer from 0 to 2^n - 1 — that’s every possible n-bit pattern.
mask & (1 << i) tests whether bit i is set in the current mask — if it is, nums[i] belongs in this subset.
No recursion at all — this is a purely iterative technique built entirely on bit manipulation.

Complexity

Time	Space
O(n × 2^n)	O(n) per subset built

Solution 2: Optimal — backtracking, include/exclude at every node

Recurse through the array, and at EVERY node of the recursion tree (not just the leaves) record the current path as a valid subset — the empty prefix, every partial selection, and every full selection are all valid subsets.

Optimal: record at every node, then include/exclude each element
    ↓
record current path  →  for each remaining element  →  include, recurse, exclude
(every node is a       (start at the NEXT index       (then backtrack)
 valid subset)         only)

Cost: O(n × 2^n) — same class as bitmask, but generalizes to
non-integer-index structures.

Interactive visualization

nums = [1, 2] — record at every recursion node: empty prefix, partial selections, and full selections are all valid subsets

Press Play or Step to begin.

Step 0 / 0

The code

function subsetsOptimal(nums) {
  const result = [];
  function dfs(start, path) {
    result.push(path.slice());
    for (let i = start; i < nums.length; i++) {
      path.push(nums[i]);
      dfs(i + 1, path);
      path.pop();
    }
  }
  dfs(0, []);
  return result;
}

Line by line:

result.push(path.slice()) happens at the TOP of every call, before the loop — this is what makes every node (not just leaves) a recorded subset.
The loop starts at i = start, never at 0 — this is what guarantees each subset is only generated once, in one canonical order, instead of once per permutation of its elements.
path.push/path.pop around the recursive call is the standard backtrack pattern: try including nums[i], explore fully, then undo before trying the next element.

Complexity

Time	Space
O(n × 2^n)	O(n) recursion depth

Complexity comparison

Solution	Time	Technique
Brute force (bitmask)	O(n × 2^n)	Iterative bit manipulation
Optimal (backtracking)	O(n × 2^n)	Recursive include/exclude

Both solutions have the EXACT same asymptotic complexity — the power set’s size alone (2^n) already forces that much work. The real difference is technique, not speed: backtracking generalizes to problems bitmask can’t handle cleanly (duplicate values, non-integer structures), while bitmask is a neat trick specific to small, simple index sets.

Interview corner

Why do both solutions have the exact same Big-O complexity?

Both must produce and return all 2^n subsets, so the output size alone already forces O(2^n) time regardless of technique.
No algorithm can beat the size of its own required output.

How would you modify the backtracking solution to only return subsets of a specific size k?

Add a length check at the top of dfs — only push path.slice() when path.length === k.
Optionally prune early too — if the remaining elements can’t possibly reach length k, stop exploring that branch, a real time-saving optimization, not just a filter.

What if the input array has duplicate values, like [1,2,2]?

Sort the array first.
In the loop, skip a duplicate value if it’s not the FIRST occurrence at this recursion depth (if (i > start && nums[i] === nums[i-1]) continue).
Otherwise the same subset gets generated more than once.

Trick question — what does this log?

const arr = Array(3).fill([]);
arr[0].push(1);
console.log(JSON.stringify(arr));

Answer: [[1],[1],[1]], not [[1],[],[]].
Array(3).fill([]) puts the exact SAME array reference into all three positions — .fill() does not call a factory function per index.
Mutating arr[0] therefore mutates the one shared array every position points to.

⚠ Trap: to get independent arrays, use Array.from({ length: 3 }, () => []) instead — that DOES call a fresh factory per index.

Quiz

1. Why do the bitmask and backtracking solutions have the exact same Big-O complexity?

A) Both must produce all 2^n subsets — the output size alone already forces O(2^n) time B) Backtracking is always faster than bitmask enumeration C) Bitmask only works for arrays of size 2 or smaller

Answer

A) Both must produce all 2^n subsets — the output size alone already forces O(2^n) time

Both must produce and return all 2^n subsets, so the output size alone already forces O(2^n) time regardless of technique. No algorithm can beat the size of its own required output.

2. In the bitmask approach, what does bit i being 1 in a mask mean?

A) nums[i] is included in the subset that mask represents B) nums[i] is excluded from the subset C) The subset has exactly i elements

Answer

A) nums[i] is included in the subset that mask represents

Bit i set to 1 means nums[i] is included in the subset that mask represents — that’s the whole mapping from integer to subset.

3. In the backtracking approach, why is path.slice() pushed into result at the START of every call, not just at the end?

A) Every node in the recursion tree — not just the leaves — represents a valid subset, including the empty prefix and every partial selection B) It’s a bug that happens to still work C) Only leaf nodes actually get recorded

Answer

A) Every node in the recursion tree — not just the leaves — represents a valid subset, including the empty prefix and every partial selection

Every node in the recursion tree — not just the leaves — represents a valid subset, including the empty prefix and every partial selection, so it must be recorded on entry, not just at the end.

4. Why does the backtracking version generalize better to problems bitmask can’t handle (like arrays with duplicates)?

A) Bitmask relies on treating include/exclude as literal bits of a fixed-size integer, which only works cleanly for small index sets; backtracking’s include/exclude recursion works for arbitrary structures B) It doesn’t — bitmask always generalizes just as well C) Backtracking is faster on large inputs

Answer

Bitmask relies on treating include/exclude as literal bits of a fixed-size integer, which only works cleanly for small index sets; backtracking’s include/exclude recursion works for arbitrary structures, including ones with duplicates or non-integer keys.

5. What causes the backtracking solution’s for-loop to start at i (via the start parameter), not always at 0?

A) To avoid generating the same subset in more than one order (e.g. both {1,2} and {2,1}) — each call only considers elements AFTER the ones already chosen B) To skip the first element of the array entirely C) It’s required to keep the recursion depth bounded

Answer

A) To avoid generating the same subset in more than one order (e.g. both {1,2} and {2,1}) — each call only considers elements AFTER the ones already chosen

Starting each call at i (via start) means every call only considers elements AFTER the ones already chosen, so a subset like {1,2} is only ever generated once, in one canonical order — never also as {2,1}.