Cracking The Coding Interview Together – Problem 8.4: Power Set

Have you ever stared at a feature flag system where combinations of permissions need to be evaluated, or a pricing engine where discount rules can be toggled on and off in every possible configuration? When we build systems that need to explore every possible permutation of choices, we quickly run into combinatorial explosion. If we aren't careful about how we generate these states, our memory fills up and our CPU spikes to 100%.

Today, we are tackling a classic foundational problem from Cracking the Coding Interview: Problem 8.4, Power Set. Writing a method to return all subsets of a set sounds deceptively simple on paper, but it forces us to confront the exponential nature of data structures head-on. By the end of this post, we will build a production-ready Java solution, analyze its mathematical limits, and learn how senior engineers reason about exponential algorithms.

Problem Statement

Write a method to return all subsets of a set. More formally, given a set of distinct integers, our goal is to return its power set—the set of all possible subsets, including the empty set and the set itself.

For example, given an input list [1, 2, 3], our method should return:

[[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]

The operational goals are clear: correctness across all edge cases (like empty inputs or single-element sets), optimal memory usage, and clean, readable code that we can proudly write on a whiteboard or in a pull request.

Analyze the Problem Together

Let's break down the constraints and find the "Aha!" conflict. First, how many subsets are there for a set of size n? Every element in the set has two choices: it is either included in a given subset, or it is excluded. This gives us $2 \times 2 \times \dots \times 2$ ($n$ times), which equals $2^n$ subsets. This means our algorithm must run in $O(2^n)$ time because that is the size of the output alone.

Now, what about naive approaches? We could try to iteratively generate subsets by picking random combinations, but that's prone to duplicates and missed states. Instead, we have two primary architectural patterns to choose from:

• The Cascading (Iterative) Approach: Start with an empty subset. Iterate through the input set. For every element we encounter, take all existing subsets, clone them, append the current element to the clones, and add them back to our master list.
• The Backtracking (Recursive) Approach: Build subsets by making a binary choice for each index: include the element or skip it. We traverse a recursion tree where every leaf node represents a valid subset.

Both approaches yield $O(n 2^n)$ time complexity, but the backtracking approach is often favored in interview settings because it directly maps to combinatorics and state-space tree traversal.

Questions for the Interviewer

Before we write a single line of code, a senior engineer always clarifies operational boundaries. Here are the questions we should ask:

• "Can we assume all elements in the input set are unique, or do we need to handle duplicate values?"
• "Should the output be returned in a specific order (e.g., lexicographical), or does order not matter?"
• "Is the input guaranteed to fit entirely in memory, or should we consider a stream-based or generator-based approach for massive sets?"
• "What is the upper bound on n? If n exceeds 30, we will overflow memory and time limits, so should we throw an exception or return a bounded stream?"

Think About the Solution

Let's design the backtracking solution. We will create a helper method that accepts the current index we are evaluating, the original input list, a temporary list holding our current subset, and a master list holding all subsets.

At each step of the recursion:

1. Add a copy of the current temporary subset to our master results list.
2. Iterate from the current index to the end of the input list.
3. For each element, include it in our temporary subset, recurse to the next index, and then backtrack by removing the element (undoing our choice).

Edge cases to consider: an empty input list [] should return [[]]. A null input should be handled gracefully by either throwing an IllegalArgumentException or returning an empty list.

Write Code and Explain

Here is the production-ready Java implementation using the backtracking pattern:

import java.util.ArrayList;
import java.util.List;

public class PowerSetGenerator {

    /**
     * Generates all subsets (the power set) of a given list of integers.
     *
     * @param set the input list of distinct integers
     * @return a list containing all possible subsets
     */
    public static List<List<Integer>> getSubsets(List<Integer> set) {
        List<List<Integer>> allSubsets = new ArrayList<>();
        if (set == null) {
            return allSubsets;
        }
        backtrack(0, set, new ArrayList<>(), allSubsets);
        return allSubsets;
    }

    private static void backtrack(int index, List<Integer> set, List<Integer> currentSubset, List<List<Integer>> allSubsets) {
        // Every state in the recursion tree represents a valid subset. Add a deep copy.
        allSubsets.add(new ArrayList<>(currentSubset));

        for (int i = index; i < set.size(); i++) {
            // Make the choice: include set.get(i)
            currentSubset.add(set.get(i));
            
            // Explore: move to the next index
            backtrack(i + 1, set, currentSubset, allSubsets);
            
            // Unmake the choice (backtrack): remove the element
            currentSubset.remove(currentSubset.size() - 1);
        }
    }

    public static void main(String[] args) {
        List<Integer> input = List.of(1, 2, 3);
        List<List<Integer>> result = getSubsets(input);
        System.out.println(result);
    }
}

Let's walk through this step by step. We initialize our allSubsets container and delegate the heavy lifting to backtrack(). Inside backtrack(), we immediately add a snapshot of currentSubset to our results. Why? Because every node we visit in this tree—not just the leaf nodes—is a valid subset. Then, we loop through remaining elements, pushing an element into our working list, diving deeper into the recursion, and popping it back out when the recursive call returns.

Time & Space Complexity

Let's analyze the performance characteristics of our solution:

• Time Complexity: $O(n \cdot 2^n)$. There are $2^n$ total subsets. For each subset, we spend $O(n)$ time to copy the elements into a new list when adding them to our result container. This is optimal because generating the output itself requires this amount of work.
• Space Complexity: $O(n \cdot 2^n)$ for storing the output result set. The auxiliary space used by the recursion stack and the temporary subset list is $O(n)$, corresponding to the maximum depth of the recursive call stack.

Why This Problem Matters (The Senior Perspective)

At first glance, generating a power set feels like an academic exercise. However, the underlying pattern—exploring combinatoric state spaces via backtracking—appears constantly in production software engineering. We use identical patterns when implementing permission authorization matrix evaluators, feature flag combination testers, query plan generators in databases, and automated test case generation tools.

When working with exponential algorithms in production, thread safety and memory management are your primary concerns. Because the output grows exponentially ($2^n$), passing large result sets across service boundaries can easily trigger OutOfMemoryError exceptions. In real-world distributed systems, we often replace recursive in-memory power set generators with lazy streams or iterators that yield subsets on demand, protecting our application heap from sudden spikes.

Final Thoughts

Mastering Problem 8.4 gives you a powerful mental model for handling recursion and state manipulation. The backtracking pattern we used here is a cornerstone of advanced algorithmic problem-solving. Take some time to modify the code above to handle input sets with duplicate values by skipping identical adjacent elements. Keep practicing, keep building, and happy coding!