Subsets and Bitmasks

The power set of a set with n elements contains every possible subset, including the empty set and the full set itself, for a total of 2^n subsets. Generating the power set is the foundation of many search and optimization problems, from scheduling to satisfiability.

Recursive Backtracking (Include / Exclude)

At each index, make a binary choice: include the current element or skip it. This naturally produces all 2^n subsets:

function subsets(nums) {
  const result = [];

  function backtrack(index, current) {
    // Record the current subset at every node (not just leaves)
    result.push([...current]);

    for (let i = index; i < nums.length; i++) {
      current.push(nums[i]);      // include nums[i]
      backtrack(i + 1, current);  // explore further
      current.pop();              // exclude nums[i] (backtrack)
    }
  }

  backtrack(0, []);
  return result;
}

console.log(subsets([1, 2, 3]));
// [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]

This is equivalent to a DFS where every node in the recursion tree is a valid subset. The depth of the tree is at most n, so the call stack uses O(n) space.

Iterative Bitmask Approach

An integer from 0 to 2^n - 1 can represent a subset: if bit j is set, element j is included. Iterating all integers in that range generates every subset without any recursion:

function subsetsBitmask(nums) {
  const n = nums.length;
  const total = 1 << n;        // 2^n
  const result = [];

  for (let mask = 0; mask < total; mask++) {
    const subset = [];
    for (let j = 0; j < n; j++) {
      if (mask & (1 << j)) {   // bit j is set → include nums[j]
        subset.push(nums[j]);
      }
    }
    result.push(subset);
  }

  return result;
}

console.log(subsetsBitmask([1, 2, 3]).length); // 8

The bitmask approach uses O(1) extra space beyond the output and is often faster in practice because it avoids function call overhead.

Handling Duplicates

If nums contains duplicates, sort first and skip building a subset that would equal one already produced. The bitmask approach becomes trickier in this case; the recursive version handles it more naturally with a seen set per level.

Complexity

Subset enumeration is O(2^n · n) — each of the 2^n subsets takes O(n) to copy. The bitmask loop is limited to n <= 31 with 32-bit integers in JavaScript (use BigInt for larger n).

Up Next

N-Queens is the classic backtracking challenge — placing queens on a board so none attack each other — with an elegant O(1) attack-check using set arithmetic.