Power Set Exploration

You're halfway through a Meta phone screen when the interviewer says, "Given an array of distinct integers, return all possible subsets." It sounds straightforward at first. But as you start thinking about the number of subsets that exist for even a small array, the combinatorial explosion becomes real. This is the Power Set problem, and it shows up at Meta, Adobe, Apple, Amazon, and Bloomberg with remarkable frequency. It tests whether you can reason about recursive enumeration and, more importantly, whether you can implement clean backtracking code under pressure.

TL;DR

Use backtracking to generate all subsets of a unique integer array. Start with an empty path, and at each recursive call, add the current path to the result. Then iterate from a start index forward, appending each element, recursing with start = i + 1, and removing the element to backtrack. This produces all 2^n subsets in O(n \times 2^n) time and space. An alternative bit manipulation approach iterates through integers 0 to 2^n - 1, using each bit to decide element inclusion.

Why This Problem Matters

The subsets problem is the gateway to an entire family of backtracking problems. Once you understand how to enumerate subsets, the jump to permutations, combinations, and combination sum becomes a matter of small adjustments. Companies like Meta and Amazon ask this problem not because the code is complex, but because it reveals how well you understand recursive state management and the include-or-exclude decision pattern.

Understanding the Problem

Given an integer array nums with all unique elements, generate every possible subset (the power set). The result should contain no duplicate subsets, and order does not matter.

For nums = [1, 2, 3]:

subsets([1,2,3]) => [[], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3]]

That is 8 subsets for 3 elements, which follows the formula: a set of n elements has 2^n subsets. Each element is either included or excluded, giving 2 choices per element.

For the simpler case of [1, 2], the recursion tree looks like this:

Even with just two elements, we already get 4 subsets: [], [1], [2], and [1,2].

Edge Cases

1. Single element: [0] produces [[], [0]]
2. Negative numbers: [-1, 0, 1] works identically since the algorithm does not depend on element values
3. Maximum constraint: With nums.length <= 10, the output can have up to 2^{10} = 1024 subsets

Solution Approach: Backtracking

The core idea behind backtracking for subsets: at each step, add the current partial subset to the result, then try extending it with each remaining element. After exploring that branch, undo the addition and try the next element.

Here is the full recursion tree for [1, 2, 3]:

Every node in this tree represents a subset that gets added to the result. The root adds [], the first level adds [1], [2], [3], and so on down to [1,2,3] at the leaves.

How Backtracking Unfolds

The step-by-step trace for backtrack(0, []) on input [1, 2, 3] shows how the algorithm explores one branch deeply, then rewinds:

The algorithm:

1. Adds [] to result
2. Picks 1, adds [1], then picks 2, adds [1,2], then picks 3, adds [1,2,3]
3. Backtracks by removing 3, then 2
4. Picks 3 from the [1] state, adds [1,3]
5. Backtracks fully, then starts from 2, adds [2], picks 3, adds [2,3]
6. Finally adds [3] on its own

This produces all 8 subsets without any duplicates. The start index prevents revisiting earlier elements, which is what eliminates duplicates structurally.

Visualizing the Backtracking Paths

The highlighted paths below show how the algorithm traverses the recursion tree depth-first, backtracking at each leaf:

The green path goes deepest first. When it hits [1,2,3], it backtracks to [1] and follows the blue path to [1,3]. After exhausting all branches from [1], it backtracks to the root and follows the purple path through [2].

Implementation

Prefer a different language? Jump to solutions in other languages.

import java.util.*;

public class Solution {

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

  private void generateSubsets(int index, int[] nums, List<Integer> current, List<List<Integer>> result) {
    result.add(new ArrayList<>(current));
    for (int i = index; i < nums.length; i++) {
      current.add(nums[i]);
      generateSubsets(i + 1, nums, current, result);
      current.remove(current.size() - 1);
    }
  }
}

Walking through the code:

1. generateSubsets starts by recording the current subset. Every call adds a snapshot of current to result. This is why the empty set is captured on the very first call.

2. The loop iterates from index to the end of the array. Starting from index (not 0) ensures we never pick an element that was already considered in an earlier position, which prevents duplicate subsets.

3. Add, recurse, remove. This is the classic backtracking triple: add nums[i] to the current path, recurse with i + 1 as the new starting index, then remove the last element to restore state before trying the next candidate.

4. new ArrayList<>(current) creates a copy. Without copying, all entries in result would point to the same list object, which ends up empty after all backtracking completes.

Alternative: Bit Manipulation

The C++ solution in this problem uses a different strategy. Instead of recursion, it iterates through all integers from 0 to 2^n - 1. Each integer is a bitmask where bit j being set means "include nums[j]."

For [1, 2, 3], the integer 5 in binary is 101, which maps to the subset [1, 3] (bits 0 and 2 are set). This approach avoids recursion entirely and is particularly clean for small n.

#include <vector>

class Solution {
public:
  std::vector<std::vector<int>> subsets(std::vector<int> &nums) {
    std::vector<std::vector<int>> result;
    int n = nums.size();
    int totalSubsets = 1 << n;

    for (int i = 0; i < totalSubsets; ++i) {
      std::vector<int> subset;
      for (int j = 0; j < n; ++j) {
        if (i & (1 << j)) {
          subset.push_back(nums[j]);
        }
      }
      result.push_back(subset);
    }

    return result;
  }
};

The outer loop runs 2^n times, and the inner loop runs n times per iteration, giving the same O(n \times 2^n) time complexity.

Alternative: Include/Exclude DFS

The Go solution takes a third approach. Instead of a loop with backtracking, it makes a binary decision at each index: include the current element or exclude it. When the index reaches the end, the current subset is complete.

This is conceptually the purest representation of why there are 2^n subsets: each element gets an independent yes/no decision.

package solution

func (s *Solution) Subsets(nums []int) [][]int {
    result := [][]int{}
    subset := []int{}
    var dfs func(int)
    dfs = func(index int) {
        if index == len(nums) {
            subsetCopy := make([]int, len(subset))
            copy(subsetCopy, subset)
            result = append(result, subsetCopy)
            return
        }
        subset = append(subset, nums[index])
        dfs(index + 1)
        subset = subset[:len(subset)-1]
        dfs(index + 1)
    }
    dfs(0)
    return result
}

Both the backtracking loop and the include/exclude DFS produce identical outputs. The loop-based approach tends to be more common in interviews because it generalizes more naturally to combinations and permutations.

Complexity Analysis

Time Complexity: O(n \times 2^n)

There are 2^n subsets in total. For each subset, we spend up to O(n) time copying it into the result list. The backtracking itself visits each node in the recursion tree exactly once, and the tree has 2^n leaf nodes. So the total work is O(n \times 2^n).

Space Complexity: O(n \times 2^n)

The result list stores all 2^n subsets, with an average subset size of n/2. The recursion stack adds O(n) depth, but this is dominated by the output size. If you exclude the output, the auxiliary space is O(n) for the recursion stack and the current path.

Backtracking vs. Bit Manipulation

Common Pitfalls

1. Forgetting to copy the current path. If you add current directly to result instead of a copy, every entry will reference the same list. After backtracking completes, all entries will be [].

2. Starting the loop from 0 instead of start. This generates subsets with elements in every possible order, producing duplicates like [2,1] alongside [1,2].

3. Not backtracking. Forgetting to remove the last element after recursion means the path grows indefinitely. You will get incorrect subsets and eventually hit stack overflow for larger inputs.

4. Off-by-one in bit manipulation. Using totalSubsets = 1 << n is correct. Using n << 1 (which equals 2 * n) is a different operation entirely and will produce wrong results.

Interview Tips

When this problem comes up in an interview:

1. Clarify the input constraints. Ask whether elements are unique. If not, you need the Subsets II variant with duplicate skipping. Also confirm whether the empty set should be included (it always should).

2. Start with the backtracking template. Sketch the recursion tree for [1, 2] first. Four subsets, easy to verify. Then explain how the start parameter prevents duplicates.

3. Mention bit manipulation as an alternative. Even if you implement backtracking, pointing out the bitmask approach shows breadth of knowledge. Interviewers at Meta in particular like hearing about both.

4. Discuss the follow-up. The interviewer will likely ask about duplicates, fixed-size subsets (combinations), or permutations. Having the backtracking skeleton fresh in your mind makes pivoting to these variations straightforward.

5. Watch your copy semantics. In Java and Python, mutable list references are a classic bug source. In Go, slice headers share underlying arrays, so copy() is essential. Mention this explicitly to show attention to detail.

Key Takeaways

• The backtracking pattern for subsets is: add current path to result, loop from start to end, add element, recurse with i + 1, remove element. This three-step cycle is the foundation for combinations, permutations, and constraint-based search problems.
• Every set of n unique elements has exactly 2^n subsets because each element independently chooses to be included or excluded. The recursion tree directly mirrors this binary choice structure.
• Bit manipulation offers a non-recursive alternative: iterate 0 to 2^n - 1, and for each bitmask, include elements whose corresponding bits are set. This is cleaner for small n but does not generalize as well to pruned search.
• The start index is what prevents duplicate subsets without sorting or a visited set. By only considering elements at index start and beyond, the algorithm ensures each combination of indices appears exactly once.
• Always copy the current path before adding it to the result. In every language, mutable references will lead to an output full of empty lists if you skip this step.

Solutions in Other Languages

Python

from typing import List

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        result = []

        def backtrack(start: int, path: List[int]):
            result.append(path[:])
            for i in range(start, len(nums)):
                path.append(nums[i])
                backtrack(i + 1, path)
                path.pop()

        backtrack(0, [])
        return result

JavaScript

class Solution {
  subsets(nums) {
    const result = [];

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

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

TypeScript

class Solution {
  subsets(nums: number[]): number[][] {
    const result: number[][] = [];

    const backtrack = (start: number, path: number[]): void => {
      result.push([...path]);
      for (let i = start; i < nums.length; i++) {
        path.push(nums[i]);
        backtrack(i + 1, path);
        path.pop();
      }
    };

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

Swift

class Solution {
    func subsets(_ nums: [Int]) -> [[Int]] {
        var result = [[Int]]()
        generateSubsets(0, nums, [], &result)
        return result
    }

    private func generateSubsets(_ index: Int, _ nums: [Int], _ current: [Int], _ result: inout [[Int]]) {
        result.append(current)
        for i in index..<nums.count {
            var nextSubset = current
            nextSubset.append(nums[i])
            generateSubsets(i + 1, nums, nextSubset, &result)
        }
    }
}

Swift's value-type arrays mean current is copied on assignment to nextSubset, so there is no need for an explicit backtrack step. The append-and-pass pattern naturally creates a fresh copy at each level.

Kotlin

class Solution {
    fun subsets(nums: IntArray): List<List<Int>> {
        val result = mutableListOf<MutableList<Int>>()
        generateSubsets(0, nums, mutableListOf(), result)
        return result
    }

    private fun generateSubsets(index: Int, nums: IntArray, current: MutableList<Int>, result: MutableList<MutableList<Int>>) {
        result.add(current.toMutableList())
        for (i in index until nums.size) {
            current.add(nums[i])
            generateSubsets(i + 1, nums, current, result)
            current.removeAt(current.lastIndex)
        }
    }
}

Ruby

class Solution
  def subsets(nums)
    result = []
    generate_subsets(0, nums, [], result)
    result
  end

  private

  def generate_subsets(index, nums, current, result)
    result.push(current.dup)
    (index...nums.length).each do |i|
      current.push(nums[i])
      generate_subsets(i + 1, nums, current, result)
      current.pop
    end
  end
end

Rust

pub struct Solution;

impl Solution {
    pub fn subsets(&self, nums: Vec<i32>) -> Vec<Vec<i32>> {
        let mut result: Vec<Vec<i32>> = Vec::new();
        Self::generate_subsets(0, &nums, &mut Vec::new(), &mut result);
        result
    }

    fn generate_subsets(index: usize, nums: &[i32], current: &mut Vec<i32>, result: &mut Vec<Vec<i32>>) {
        result.push(current.clone());
        for i in index..nums.len() {
            current.push(nums[i]);
            Self::generate_subsets(i + 1, nums, current, result);
            current.pop();
        }
    }
}

Rust requires explicit ownership management. The current.clone() call creates an owned copy for the result, while &mut references allow in-place modification during backtracking.

Scala

The Scala solution uses a functional approach without mutation, passing immutable lists through recursive calls:

class Solution {
  def subsets(nums: Array[Int]): List[List[Int]] = {
    def backtrack(start: Int, current: List[Int], result: List[List[Int]]): List[List[Int]] = {
      if (start == nums.length) {
        result :+ current
      } else {
        val withCurrent = backtrack(start + 1, current :+ nums(start), result)
        backtrack(start + 1, current, withCurrent)
      }
    }
    backtrack(0, List.empty, List.empty)
  }
}

C#

public class Solution {
    public List<List<int>> Subsets(int[] nums) {
        var result = new List<List<int>>();
        GenerateSubsets(0, nums, new List<int>(), result);
        return result;
    }

    private void GenerateSubsets(int index, int[] nums, List<int> current, List<List<int>> result) {
        result.Add(new List<int>(current));
        for (int i = index; i < nums.Length; i++) {
            current.Add(nums[i]);
            GenerateSubsets(i + 1, nums, current, result);
            current.RemoveAt(current.Count - 1);
        }
    }
}

Dart

class Solution {
  List<List<int>> subsets(List<int> nums) {
    List<List<int>> result = [];
    generateSubsets(0, nums, [], result);
    return result;
  }

  void generateSubsets(int index, List<int> nums, List<int> current, List<List<int>> result) {
    result.add(List.from(current));
    for (int i = index; i < nums.length; i++) {
      current.add(nums[i]);
      generateSubsets(i + 1, nums, current, result);
      current.removeLast();
    }
  }
}

PHP

class Solution {
    public function subsets(array $nums): array {
        $result = [];
        $this->generateSubsets(0, $nums, [], $result);
        return $result;
    }

    private function generateSubsets(int $index, array $nums, array $current, array &$result): void {
        $result[] = $current;
        for ($i = $index; $i < count($nums); $i++) {
            $current[] = $nums[$i];
            $this->generateSubsets($i + 1, $nums, $current, $result);
            array_pop($current);
        }
    }
}

PHP passes arrays by value by default, so $current is copied when assigned to $result[]. The &$result reference parameter ensures all recursive calls share the same output array.

Practice Makes Perfect

Once you have the subsets pattern down, the natural next steps are:

• Subsets II - handle duplicate elements with a sorting + skip strategy
• Permutations - generate all orderings instead of all selections
• Combination Sum - find subsets that add up to a target value
• Letter Combinations of a Phone Number - backtracking over a different kind of choice space

The backtracking skeleton stays the same across all of these. The only things that change are the loop bounds, the termination condition, and the constraints on what gets added.

This problem and many others are available on Firecode, where over 50,000 engineers have prepared for technical interviews and landed roles at top tech companies. Consistent practice with these patterns is what separates candidates who struggle with backtracking from those who solve it in five minutes flat.