A feature-flag service had to emit every subset of distinct flags so QA could run a matrix. The intern numbered each subset as an integer from 0 to 2^n - 1 and packed set bits into lists. n = 4 was sixteen rows before coffee. n = 20 is a million masks, and the talk at the board was “I looped integers” instead of “I take or skip the next flag.”

Subsets asks for the power set of a distinct array. An array of n values already names the bits. Masks use that and still hide the decision tree.

This is an interview writeup, not a backtracking lecture. The backtracking post owns choose, recurse, and undo — including the pick-or-skip sketch. Here we only care about snapshotting the path so each prefix (or each leaf) is a subset you can return.

The problem

Given an int[] nums of distinct integers, return all possible subsets. The empty subset is part of the answer. Order of subsets, and order inside a subset, does not matter. The same set of values must not appear twice.

nums = [1, 2, 3]  →  [], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]
nums = [0]        →  [], [0]

Note: If nums can repeat, that is Subsets II: sort and skip a duplicate at the same depth. This prompt promised distinct values, so take-or-skip never emits the same set twice.

Bit masks do the same 2^n work

Each integer mask in 0 .. 2^n - 1 is a subset: bit j set means nums[j] is in. Correct. You still visit 2^n sets. The interview talk is a bit loop, not a path.

List<List<Integer>> subsetsMask(int[] nums) {
    List<List<Integer>> out = new ArrayList<>();
    int n = nums.length;
    int limit = 1 << n;
    for (int mask = 0; mask < limit; mask++) {
        List<Integer> row = new ArrayList<>();
        for (int j = 0; j < n; j++) {
            if (((mask >> j) & 1) == 1) {
                row.add(nums[j]);
            }
        }
        out.add(row);
    }
    return out;
}

At n = 4 this is sixteen scans. At n the board cares about, you paid a mask generator for a question a path answers by taking or skipping: is nums[i] in this subset or not?

Take or skip, and copy the path

Index i is the next value. Append it, recurse i + 1, pop (the take). Then recurse i + 1 without it (the skip). When i == n, copy the path — that leaf is one subset. Skip every index and the leaf is [].

A start-index loop is the same tree with the snapshot at every node: record path, then for i from start append nums[i] and recurse i + 1. You do not wait for the leaf. Same 2^n copies.

Walk [1, 2]. Four leaves.

nums = [1, 2]   path = []

i=0  take 1     path=[1]
  i=1  take 2   path=[1,2]  i=2 record [1,2]
       skip 2   path=[1]    i=2 record [1]
     pop 1
     skip 1     path=[]
  i=1  take 2   path=[2]    i=2 record [2]
       skip 2   path=[]     i=2 record []

The Java is the take-or-skip walk:

List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> out = new ArrayList<>();
    walk(0, nums, new ArrayList<>(), out);
    return out;
}

void walk(int i, int[] nums, List<Integer> path, List<List<Integer>> out) {
    if (i == nums.length) {
        out.add(new ArrayList<>(path));
        return;
    }
    path.add(nums[i]);
    walk(i + 1, nums, path, out);
    path.remove(path.size() - 1);
    walk(i + 1, nums, path, out);
}

Time is Θ(n · 2^n) — 2^n subsets, each copied in O(n). Extra space is O(n) for the path and the call stack, besides the output. Masks cost the same copies; they are not a cheaper class.

Note: out.add(path) aliases the live list. Later pops empty every recorded subset. Forget the pop on the take branch and every skip inherits a value you meant to refuse.

What interviewers usually poke next

  • Start-index loop. Record at every node, then for (int i = start; ...). Same power set. Say why you copy before the loop: that snapshot is the subset that skips everyone from start onward.
  • Duplicates in nums. Sort. At a given depth, skip nums[i] == nums[i - 1] when i > start. Take-or-skip without that skip emits [1, 2] twice from [1, 1, 2].
  • Subsets of size k only. Stop when path.size() == k, or bound the start-index loop. Combinations, not the full power set.
  • Bit masks. Same work. Fine if you can name the bit. The usual board answer is the path, because the next prompt (duplicates, size k, constraints) extends the undo, not the integer.

You are done with this problem when you can walk take-and-skip on [1, 2] out loud, say why the empty list is a recorded leaf, and say why a mask loop is the same 2^n with a weaker story.