Finding All Combinations with the The Selection Pattern

How to recursively explore every possible subset using include/exclude decisions.

Hi Friends,

Welcome to the 169th issue of the Polymathic Engineer newsletter. This week, we continue our recursion series with the third article.

In the previous two articles, we discussed the basics of recursion and looked at the first two patterns: Iteration and Subproblems. While these patterns are useful, they don’t go very deep. Now we move on to a stronger pattern: Selection.

Selection is arguably the most important recursive pattern you can learn. It frequently comes up in coding interviews, and it is the basis for dynamic programming. A lot of problems that seem hard at first become easy once you realize that they are selection problems in disguise.

The core concept is easy to understand. You look at a set of items and decide whether or not to include each one in your result. By exploring every possible combination of these choices, you generate every possible subset of the original set. From there, you can filter, count, or optimize to get the answer you need.

This article will explore how this pattern works and how to apply it to real problems.

The outline is as follows:

• The core selection pattern

• Counting combinations

• Generating Combinations

• Combinations of a specific length

• The 0/1 Knapsack problem

• When selection applies

---

Project-based learning is the best way to develop technical skills. CodeCrafters is an excellent platform for tackling exciting projects, such as building your own Redis, Kafka, a DNS server, SQLite, or Git from scratch. Sign up, and become a better software engineer.

---

The Core Selection Pattern

The selection pattern answers a specific type of question: “Can this problem be solved by finding all possible combinations?” If the answer is yes, then you can use the same approach every time.

The starting point is a set of items. For each item, you have two options: include it in the result or leave it out. You go through the items one by one, and at every step, you branch into two paths. One includes the current item, and the other path excludes it.

As a concrete example, consider the array [1, 2, 3]. You start at the first item. You can either include 1 or exclude it. If you include it, your partial result is [1]. If you exclude it, your partial result is [].

Now you move to the second item. For each of the two partial results, you again have two choices. Include or exclude 2. This gives you four partial results: [1, 2], [1], [2], and []. You continue this process for the third item. Each of the four results branches into two, and you end up with eight total combinations: [1, 2, 3], [1, 2], [1, 3], [1], [2, 3], [2], [3], and []. This is the complete set of subsets.

There are always 2^n subsets for an array of n elements, including the empty set. The selection pattern generates all of them by examining every possible path through the decision tree.

The word “selection” comes from the choice you make at each step. You are selecting which items to include in your result. People also call this the "combinations" pattern, but I prefer "selection" because it captures what you do: you either choose the item, or you don't.

Counting Combinations

Before looking at how to generate all the combinations, it helps to start with a simpler task: counting how many combinations exist. This is a good approach since it lets you focus on the recursive structure without worrying about building up results.

The logic is straightforward. You return 1 if you have reached the end of the array and discovered one valid combination. Otherwise, you make two recursive calls, one which includes the current item and one that excludes it. You add the results together.

def count_combinations(arr, i=0):
    if i == len(arr):
        return 1

    include = count_combinations(arr, i + 1)
    exclude = count_combinations(arr, i + 1)

    return include + exclude

Let’s trace what happens when we run this code with the array [1, 2, 3]. The initial call branches into two: one where we include 1 and one where we don't. Then we move to item 2, and each of those branches splits into two other branches. The same happens for item 3. When we reach the end of the array, we return 1. All those 1s add up as the calls return, and we get 8 at the top.

You might notice that the include and exclude calls are identical. That is because the number of remaining combinations stays the same regardless of whether you include an item. There are always the same number of paths forward. This will not hold when we add constraints.

The time complexity is O(2^n) because we make two recursive calls at each level, and the depth is n. The space complexity is O(n) because of the call stack. These numbers match what we expect: there are 2^n combinations, and we visit each one.

Generating Combinations

Counting is straightforward, but for most problems, you need to actually generate the combinations. This is where things get more interesting. There are two main ways to do this: either build up the results as you return them, or update a passed variable as you go.