Generating Subsets via Recursion

Hello! In our previous lesson, we analyzed the performance of recursive functions by examining their call trees, distinguishing between time complexity (total calls) and space complexity (maximum depth). We ended with a look at a function to generate binary strings, which demonstrated a key recursive pattern: making two choices at each step.

Today, we'll formalize that pattern and apply it to solve a classic combinatorial problem. You will learn how to generate all subsets of a given set of elements using a powerful recursive technique called "choose-or-skip". This is your first formal step into the world of backtracking, a fundamental algorithmic approach for exploring all possible solutions to a problem by incrementally building candidates and abandoning ("backtracking" from) those that cannot be completed.

The Core Idea: Two Choices for Every Element

Imagine you have a set of numbers, for example, {1, 2, 3}. To form any subset, you can go through the numbers one by one and make a simple decision for each: do I include this number in my subset, or do I exclude it?

This sequence of binary choices creates a decision tree. Let's visualize this process.

If you trace any path from the top to a leaf at the bottom, the sequence of choices uniquely defines a subset. For example:

• Exclude 1, Include 2, Exclude 3 → {2}
• Include 1, Include 2, Include 3 → {1, 2, 3}

This "two choices at each step" structure is identical to the one we saw when generating binary strings. You can think of "include" as choosing '1' and "exclude" as choosing '0'. This reveals a deep connection: finding all subsets of n elements is equivalent to generating all n-bit binary numbers. Since there are $2^n$ such numbers, we expect to find $2^n$ subsets.

From Decision Tree to Recursive Structure

This decision tree translates directly into a recursive function. To navigate the tree, our function needs to keep track of its current position. This "state" consists of two key pieces of information:

1. index: Which element of the input array are we currently making a decision about?
2. currentSubset: The list of elements we have chosen to include so far along the current path.

Our recursive function, let's call it dfs (for Depth-First Search), will have the following structure:

• Base Case: We've made a decision for every element. This happens when our index goes past the end of the input array. At this point, the currentSubset is a complete, valid subset, and we add it to our final list of results.
• Recursive Step (The Two Choices):
  1. The "Exclude" path: We decide not to include the element at the current index. To do this, we simply move on to the next element by making a recursive call: dfs(index + 1, currentSubset).
  2. The "Include" path: We decide to include the element at index. We first add it to our currentSubset, and then we move on to the next element by making a recursive call: dfs(index + 1, currentSubset).

This leads to the most important step in all of backtracking.

The Backtracking Step: Undoing a Choice

After the "Include" path's recursive call dfs(index + 1, ...) returns, we have fully explored that entire branch of the decision tree. Our currentSubset still contains the element we just added. If we do nothing, this element will incorrectly persist as we return up the call stack and explore other branches.

We must undo our choice. This is the "backtrack" step. By removing the element we just added, we restore the state of currentSubset to what it was before we went down the "Include" path. This allows the "Exclude" path of the parent call to function correctly.

This "Choose → Explore → Unchoose" cycle is the essence of backtracking.

Let's dive into a full explanation and implementation. The following reading from Algo.monster provides an excellent, in-depth walkthrough of this pattern, including the TypeScript code and a detailed discussion of common pitfalls.

The pitfalls section highlights two points that are especially relevant given your extensive development experience.

1. Creating a Copy of the Subset: In JavaScript and TypeScript, arrays are passed by reference. If you push currentSubset directly into your results array, you are just pushing a pointer. When you later modify currentSubset by popping elements, those changes will be reflected in the results array! This is why result.push([...currentSubset]) is necessary; it creates a new array (a shallow copy) with the current contents.
2. The pop() Backtracking Step: Forgetting to pop() the element after the "include" path returns is a classic backtracking bug. It corrupts the state for all subsequent explorations. The currentSubset array must be restored to its previous state before the function returns.

For another excellent perspective, the following video from NeetCode walks through the exact same logic, drawing the decision tree and then coding the solution. Seeing the logic explained in a different voice can often help it click.

Complexity Analysis

Let's briefly connect this back to our previous lesson on complexity.

• Time Complexity: $O(n\cdot 2^n)$
  As we established, there are $2^n$ subsets. To build each subset, we traverse a path of length n in our decision tree. When we find a complete subset at a leaf node, we create a copy of it to add to our results. In the worst case, a subset can have n elements, so the copy operation takes $O(n)$ time. Multiplying these factors gives us a total time complexity of $O(n\cdot 2^n)$.

• Space Complexity: $O(n)$
  This is the auxiliary space, not including the output array. The maximum depth of our recursion is n (the height of the decision tree). This means the call stack will grow to at most size n. The currentSubset array we use to build candidates will also hold at most n elements. Therefore, the space complexity is dominated by the recursion depth, making it $O(n)$.

The following video provides a concise breakdown of this complexity analysis and implements the pattern using a generic template, which is a great way to think about these problems.

Conclusion

In this lesson, you've learned your first formal backtracking pattern: choose-or-skip. This powerful recursive strategy allows you to systematically explore all possible subsets of a set by making a binary decision for each element.

Here are the key takeaways:

• The Model: Generating subsets can be modeled as a decision tree where each node represents a choice to either include or exclude an element.
• The State: A recursive backtracking function for this problem needs to track the index of the current element and the currentSubset being built.
• The Pattern: The core logic is a "Choose, Explore, Unchoose" cycle. For the "include" path, you add an element, make a recursive call, and then critically remove that element to backtrack and clean up the state.
• The Implementation: Remember to push a copy of your candidate subset to the final results to avoid reference issues.

In our next lesson, we will adapt this backtracking template to solve a related problem: generating all permutations of a set. While subsets are about choosing elements (where order doesn't matter), permutations are about arranging them (where order is everything). You'll see how a small change to our state-tracking logic allows us to solve this new problem.