Combinations Using Backtracking

In our previous lessons, we built a solid foundation in backtracking by generating all subsets of a set, first with unique elements and then handling duplicates. The core of our approach was a decision-making process at each step: either include or exclude an element. Today, we'll adapt this framework to solve a closely related and fundamental problem: generating combinations.

Our learning outcome for this lesson is to generate all combinations of k elements from a set using backtracking. Instead of generating subsets of all possible sizes (from 0 to n), our new goal is to find only those subsets that have a specific size, k. This seemingly small change requires us to refine our base cases and, in some cases, our entire recursive structure to be more efficient. This is a classic interview problem that tests your ability to precisely control a backtracking search.

From Subsets to Combinations: Adding a Constraint

At its heart, the "Combinations" problem (like LeetCode #77, Combinations) is a subset problem with an additional constraint. Let's revisit our backtracking mental model:

• Choices: For each number in our input set (e.g., numbers from 1 to n), what are our options?
• Constraints: What rules must our solution follow?
• Goal: What defines a complete and valid solution?

For the combinations problem with parameters n and k:

• Choices: For each number, we can decide to include it in our current combination.
• Constraints:
  1. The numbers must be chosen from the range [1, n].
  2. The order of elements within a combination doesn't matter (e.g., [1, 2] is the same as [2, 1]).
  3. The final combination must contain exactly k elements.
• Goal: We have reached a goal state when we have successfully built a combination of size k.

The key change from the subset problem is the new constraint on size. Our backtracking algorithm must now terminate and record a solution only when the current path has accumulated exactly k elements.

Visualizing the Combination Search Tree

The process of building combinations can be visualized as exploring a search tree. We start with an empty combination and, at each level, we make a decision about which number to add next. To avoid duplicates and permutations (like [1, 2] and [2, 1]), a common strategy is to only add numbers that are greater than the one just added.

The image below illustrates this for n=4 and k=3. The tree systematically explores paths, adding one number at a time. Once a path reaches a length of 3 (our k), it's a valid solution. The algorithm then backtracks to explore other branches.

The Canonical Approach: Iterative Choice

While the "include/exclude" pattern from our subset lessons can be adapted, a more natural and efficient pattern for combinations involves an iterative loop within the recursive function. This pattern is often more intuitive for problems where you need to pick k items from n.

Let's define a recursive function backtrack(start, current_combination):

• start: The number we can begin choosing from. This ensures we only move forward (e.g., after picking 2, we only consider 3, 4, ...), which elegantly handles the "order doesn't matter" constraint.
• current_combination: The list of numbers we've chosen so far.

The logic is as follows:

1. Base Case: If len(current_combination) == k, we have found a valid combination. Add a copy of it to our results and return.
2. Recursive Step: Iterate with a loop from i = start to n. In each iteration:
   • Add the number i to current_combination.
   • Make a recursive call: backtrack(i + 1, current_combination). The i + 1 is crucial; it ensures the next choice is always greater than the current one.
   • Backtrack: Remove i from current_combination so we can explore the next choice in the loop (e.g., after exploring all paths starting with [1, 2], we pop 2 to get back to [1], allowing the loop to then explore paths starting with [1, 3]).

The NeetCode video below provides an excellent walkthrough of this exact logic, using a decision tree to make the process crystal clear.

Now that you have the intuition, let's look at a clean implementation of this pattern.

An Important Optimization: Pruning

The algorithm we've just discussed is correct, but we can make it more efficient by "pruning" branches of the search tree that cannot possibly lead to a valid solution.

Consider this scenario: n=10, k=4. Suppose our current_combination is [8] and we are about to make our next choice starting from i=9.

• We need 4 - 1 = 3 more numbers.
• We only have 10 - 9 + 1 = 2 numbers left to choose from (9 and 10).

Since we need 3 numbers but only 2 are available, there's no point in continuing down this path. We can prune this branch of the search tree.

The general rule for pruning is:
If (k - len(current_combination)) > (n - i + 1), then stop.

• (k - len(current_combination)) is the number of elements we still need.
• (n - i + 1) is the number of elements available to choose from.

While you can implement this as an explicit if check, the "include/exclude" pattern offers a clever way to handle this implicitly. The following video explains a backtracking approach that builds this pruning into its structure.

Adapting the "Include/Exclude" Pattern

For completeness, let's see how our familiar "include/exclude" pattern from the subsets lessons can be adapted. The AlgoMonster resource below details this approach.

While this pattern works, it tends to be less efficient for the combinations problem because it explores many paths that will never reach size k. The iterative choice pattern is generally preferred here as it builds the combination more directly. However, knowing you can adapt this pattern is valuable.

Complexity Analysis

• Time Complexity: $O(k\cdot (\genfrac{}{}{0ex}{}{n}{k}))$

  • The number of possible combinations is given by the binomial coefficient $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$, which is "n choose k". Our algorithm must generate each of these.
  • For each valid combination found, we spend $O(k)$ time to create a copy and add it to our results list.
  • Therefore, the total time is the number of solutions multiplied by the cost to store each one.

• Space Complexity: $O(k)$

  • This is the auxiliary space used by the algorithm, not including the output list.
  • The maximum depth of the recursion call stack will be k.
  • The current_combination list will also hold at most k elements.

Conclusion

In this lesson, you have successfully adapted your backtracking skills to handle problems with a fixed-size constraint. You've seen how a small change in the problem statement—requiring subsets of a specific size k—translates into a crucial modification of the backtracking base case.

Key Takeaways:

• Combinations as Constrained Subsets: The problem of finding all combinations of size k is a special case of the subset problem where the goal is only reached when the path length equals k.
• Iterative Choice Pattern: A highly effective pattern for combination problems is to use a for loop within your recursive function (backtrack(start, ...)), which naturally prevents duplicate elements and permutations.
• Pruning is Key: For an efficient solution, you can prune the search space by checking if it's still possible to form a valid combination with the remaining elements.
• Pattern Adaptability: You saw how the "include/exclude" pattern could also be made to work, demonstrating the flexibility of these core backtracking templates.

In our next lesson, we will tackle permutations. While combinations are about choosing elements, permutations are about arranging them. This will require us to introduce a new mechanism to keep track of which elements have already been used in the current path.