Combination Sum with Pruning

Hello! In our last lesson, we mastered generating combinations of a fixed size k. We saw how a simple constraint on the length of our solution path transforms the subset problem into the combination problem. Today, we'll continue our journey into backtracking by tackling another common variation: finding combinations that sum up to a specific target value.

This lesson focuses on the learning outcome: Generate combinations that sum to a target, using pruning to optimize the search. We will explore a powerful and common interview problem, often called "Combination Sum". The core challenge lies not just in finding the combinations, but in doing so efficiently by avoiding redundant computations and handling duplicate numbers in the input. This requires a smart use of pruning, a technique we'll explore in depth.

From Fixed Size to Target Sum

In previous lessons, our goal was defined by the number of elements in our combination. Now, the goal is defined by the sum of those elements. This shifts our base case from checking len(path) == k to checking current_sum == target.

This category of problems has a few variations, but we will focus on the most instructive one, often called "Combination Sum II" (like LeetCode #40). Its rules are:

1. You are given an array of numbers (candidates) which may contain duplicates.
2. Each number in candidates can be used at most once in each combination.
3. The goal is to find all unique combinations that sum to a target.

This problem is a perfect extension of our previous work because it forces us to combine the "choose/don't choose" logic with two new critical techniques: advanced pruning and a robust strategy for handling duplicates.

The Foundational Strategy: Sort, Recurse, Prune

A highly effective approach for this problem rests on a three-part strategy. Before we even start backtracking, we must sort the input candidates array. Sorting is not just an optimization; it is the key that unlocks both efficient pruning and a simple way to handle duplicates.

Once sorted, our backtracking function will look familiar. We can define it as backtrack(start_index, remaining_target):

• start_index: The index in candidates from which we can start choosing numbers. This prevents us from generating permutations (like [1, 7] and [7, 1]).
• remaining_target: The value we still need to reach the original target.

The core of the algorithm will be a loop that iterates from start_index and makes a choice at each step: include the current number candidates[i] and recurse, or skip it.

The AlgoMonster article on "Combination Sum II" provides an excellent in-depth explanation of this entire process.

Advanced Pruning and Handling Duplicates

Let's look closer at the two most important aspects of this algorithm: pruning and duplicate handling.

Pruning the Search Tree

Pruning is about making our algorithm "smarter" by not exploring paths that are guaranteed to fail. With a sorted candidates array, if we find that the current number candidates[i] is greater than the remaining_target, we know that every subsequent number will also be too large. There is no need to check them. We can immediately stop exploring this branch of the recursion and backtrack.

The image below visualizes this. We are trying to find combinations that sum to a target of 5. When the current path is [2] and the remaining target is 3, we consider adding 5. Since 5 > 3, this path (and any subsequent choices from this node) is pruned (indicated by the red arrow).

Handling Duplicates in the Input

This is often the trickiest part to implement correctly. Our goal is to avoid duplicate combinations in the final result (e.g., if candidates = [1, 2, 2] and target = 3, we want only [1, 2], not [1, 2] twice).

Since we sorted the array, all duplicate numbers are now adjacent. The logic to avoid generating duplicate combinations is this: within a single recursive call's for loop, after we use a number, we must skip all subsequent identical numbers.

Consider candidates = [1, 2, 2', 7] and target = 9.

• The loop starts, and we build a path with [2]. We recursively find all combinations starting with [2], such as [2, 7].
• After that recursion returns, the loop continues to the next element, 2'.
• If we were to start a new recursive path with [2'], we would find [2', 7], which is a duplicate of [2, 7].
• The condition if i > start_index and candidates[i] == candidates[i - 1] prevents this. When the loop moves from 2 to 2', this condition becomes true, and we continue, skipping the redundant search.

The i > start_index part is subtle but crucial. It ensures that we can use duplicate numbers as part of a single combination (e.g., [1, 1, 6] if the input contains two 1s), but we just don't start new top-level branches with them.

The following walkthrough will make this concrete.

Pattern Recognition: The Backtracking Family

As you've seen, many backtracking problems share a similar structure. Recognizing these patterns is key to solving them quickly in an interview setting. Let's look at a summary table that compares the problems we've covered so far.

Notice the row for Combination Sum II. The "Special Rule" is "Sort the input," and we "Explore with next element" (idx + 1). This contrasts with Combination Sum (the first version of the problem), where you can reuse elements. In that version, the recursive call would be backtrack(idx, ...) instead of backtrack(idx + 1, ...), allowing the same element to be chosen again. The distinction between i and i+1 in the recursive call is a fundamental pattern for controlling whether elements can be reused.

Conclusion

In this lesson, we've extended our backtracking toolkit to solve "Combination Sum" problems. You learned how to adapt the base case to a target sum and, more importantly, how to use sorting as a powerful tool for both pruning and duplicate handling.

Key Takeaways:

• Sort First: For combination sum problems with unique usage constraints and potential duplicates, sorting the input array is almost always the best first step.
• Pruning is Power: A sorted array allows for efficient pruning. If the current candidate is larger than the remaining target, you can stop that search path immediately.
• Duplicate Handling Logic: The if i > start_index and candidates[i] == candidates[i-1] pattern is the standard, elegant way to avoid duplicate combinations when the input contains duplicate numbers.
• i vs. i+1: The choice of passing i or i+1 to the next recursive call is a critical pattern that controls whether an element can be reused within a combination. For "Combination Sum II", we use i+1.

In our next lesson, we will shift our focus from choosing elements (combinations) to arranging them. We will learn how to generate all permutations of a list, which will require a new strategy for tracking which elements have already been used in the current arrangement.