medium Subsets

Subsets via Bitmask

Problem. Given an array nums of distinct integers, return the power set — every possible subset, including the empty set and the full set. For nums = [1, 2, 3] there are 23 = 8 subsets. Order of the subsets in the output does not matter. (LeetCode 78.)

This is the direct payoff of the bitmasking page: a subset is an n-bit number, so generating the power set is nothing more than counting from 0 to 2n−1 and reading each integer’s bits. But the interviewer’s real question is almost never “can you produce subsets” — it is “bitmask or backtracking, and why?” That judgment is the substance of this page.

The naive baseline — and why it is not really “naive”

The recursive/backtracking construction is the textbook first answer: at each element decide take it or skip it, recursing down a binary decision tree of depth n. Every node of that tree is a valid subset, so you snapshot the current path at every node. It is O(n · 2n) time (there are 2n subsets and copying each costs up to O(n)) and uses O(n) recursion stack. That is already optimal in time — you cannot beat the output size. So the bitmask version is not asymptotically faster; it is a different shape with different trade-offs, which is exactly why the choice is interesting.

The bit insight

Bijection: each subset ↔ one n-bit mask, element i present iff bit i is set. The masks 0..2n−1 are precisely the n-bit patterns, so looping that range emits every subset exactly once — no recursion, no explicit “undo,” no stack. The outer loop picks the mask; an inner loop over the n bit positions reads which elements the mask selects.

Traced example — nums = [1, 2, 3]

Index the array so nums[0]=1, nums[1]=2, nums[2]=3. Bit i controls nums[i]:

Eight masks, eight subsets, output [[], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3]]. Notice the emission order differs from backtracking’s (which yields [], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]) — both are correct power sets; the problem does not constrain order.

Java: bitmask power set

import java.util.*;

public class Subsets {
    public List<List<Integer>> subsets(int[] nums) {
        int n = nums.length;
        List<List<Integer>> result = new ArrayList<>();
        for (int mask = 0; mask < (1 << n); mask++) {   // 2^n masks
            List<Integer> subset = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                if ((mask & (1 << i)) != 0) {           // bit i set -> take nums[i]
                    subset.add(nums[i]);
                }
            }
            result.add(subset);
        }
        return result;
    }

    public static void main(String[] args) {
        System.out.println(new Subsets().subsets(new int[]{1, 2, 3}));
        // [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]
    }
}

Go: bitmask power set

package main

import "fmt"

func subsets(nums []int) [][]int {
	n := len(nums)
	var result [][]int
	for mask := 0; mask < (1 << n); mask++ { // 2^n masks
		var subset []int
		for i := 0; i < n; i++ {
			if mask&(1<<i) != 0 { // bit i set -> take nums[i]
				subset = append(subset, nums[i])
			}
		}
		result = append(result, subset)
	}
	return result
}

func main() {
	fmt.Println(subsets([]int{1, 2, 3}))
	// [[] [1] [2] [1 2] [3] [1 3] [2 3] [1 2 3]]
}

The named alternative — backtracking

Worth writing out, because the judgment call is only meaningful if you can produce both. Every recursion node is emitted as a subset; the for loop chooses the next element to append, recurses, then undoes the choice so the next iteration starts clean.

Java: backtracking power set

import java.util.*;

public class SubsetsBacktrack {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(nums, 0, new ArrayList<>(), result);
        return result;
    }

    private void backtrack(int[] nums, int start,
                           List<Integer> cur, List<List<Integer>> result) {
        result.add(new ArrayList<>(cur));        // snapshot: every node is a subset
        for (int i = start; i < nums.length; i++) {
            cur.add(nums[i]);                    // choose
            backtrack(nums, i + 1, cur, result); // explore
            cur.remove(cur.size() - 1);          // un-choose (backtrack)
        }
    }

    public static void main(String[] args) {
        System.out.println(new SubsetsBacktrack().subsets(new int[]{1, 2, 3}));
        // [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]
    }
}

Go: backtracking power set

package main

import "fmt"

func subsets(nums []int) [][]int {
	var result [][]int
	var cur []int
	var backtrack func(start int)
	backtrack = func(start int) {
		// snapshot: MUST copy, cur's backing array is mutated in place
		subset := make([]int, len(cur))
		copy(subset, cur)
		result = append(result, subset)
		for i := start; i < len(nums); i++ {
			cur = append(cur, nums[i]) // choose
			backtrack(i + 1)           // explore
			cur = cur[:len(cur)-1]     // un-choose
		}
	}
	backtrack(0)
	return result
}

func main() {
	fmt.Println(subsets([]int{1, 2, 3}))
	// [[] [1] [1 2] [1 2 3] [1 3] [2] [2 3] [3]]
}

Complexity — both are output-optimal

• Bitmask: 2n masks × O(n) to read bits and build each subset → O(n · 2n) time. Auxiliary space beyond the output is O(1) (a mask and a loop index) — no recursion stack.
• Backtracking: 2n nodes, each snapshot up to O(n) → O(n · 2n) time, plus O(n) recursion-stack space.
• The output itself contains 2n subsets totalling n · 2n−1 integers, so O(n · 2n) is a lower bound — neither approach can be asymptotically faster. The difference is constant factors and shape, not order.

Judgment layer — when to reach for the bitmask, and when not

• Reach for the bitmask when n is small and you want a clean, iterative, stack-free enumeration — especially if you also need a canonical integer id per subset (the mask). That id is gold when subsets feed a DP table, a memo, or a dedup HashSet: the mask is the key. It also has the better constant factor (no function-call overhead) and O(1) auxiliary space.
• Reach for backtracking when you need to prune. The bitmask loop is committed to producing all 2n masks — it cannot skip a branch. If the problem adds a constraint (“subsets that sum to T,” “subsets of size exactly k,” “stop when the partial sum exceeds a bound”), backtracking abandons whole subtrees early and can explore far fewer than 2n nodes. The bitmask would still grind through all of them.
• Backtracking also generalizes past the int-width wall. The bitmask is capped at n ≤ ~31 (a 32-bit mask; 1 << n overflows beyond that). Backtracking has no such ceiling — not that 2n is ever tractable for large n, but the recursion structure extends naturally to permutations, combinations, and constraint search, where bitmask enumeration does not.
• Duplicates (Subsets II). If nums can contain repeats, backtracking handles it cleanly: sort, then in the loop skip nums[i] == nums[i-1] at the same tree level. The bitmask version would generate duplicate subsets and need a separate dedup pass — a point in backtracking’s favor when the input is not distinct.
• Interview default: state both, then pick backtracking as the primary answer unless you specifically want subset-ids or are already living in a bitmask-DP problem — because backtracking is the one that keeps working when the follow-up adds a constraint, which the follow-up almost always does.

Edge cases & traps

• Empty input. nums = [] → n = 0, 1 << 0 = 1, one mask (0) → output [[]]. The power set of the empty set is the set containing the empty set — not an empty list.
• The Go snapshot copy is mandatory. append(result, cur) without copy stores a slice that shares cur’s backing array; the later cur = cur[:len-1] and subsequent appends mutate it in place, silently corrupting every previously stored subset. Always copy the path before recording it.
• Operator precedence (a Java trap). In Java, & binds looser than !=, so mask & (1 << i) != 0 parses as mask & ((1<<i) != 0) — a compile error. Parenthesize: (mask & (1 << i)) != 0. Go reverses the precedence (& binds tighter than !=), so the bare form happens to compile and work there — but parenthesize regardless, for clarity and portability.
• 1 << n overflow. For n ≥ 31 the shift overflows a 32-bit int; but generating 231 subsets is infeasible regardless, so treat large n as a signal to switch algorithms, not to widen the type.

Takeaways

• Power set = count 0..2n−1, read each mask’s bits. Iterative, no stack, a free integer id per subset.
• Same O(n · 2n) time as backtracking — the choice is about pruning, ids, and duplicates, not asymptotics.
• Bitmask shines for small n, subset-ids, and bitmask DP; backtracking shines when you can prune, when duplicates exist, and when constraints get added.

Standard power-set formulation (LeetCode 78) re-derived from the set/int bijection, paired against the backtracking alternative; all four samples were compiled and run to confirm the emitted subsets.