# Combination Sum I Explained in Depth with Intuition and Code Solution

When diving into algorithmic problems, the challenge of finding combinations of numbers that sum up to a specific target often arises. One such problem is known as Combination Sum I, a classic problem that tests our understanding of recursion and backtracking. In this post, we’ll explore the problem in-depth, break down its intuition, and provide a clear code solution.

## Problem Statement

The Combination Sum I problem can be formally stated as follows:

Given an array of distinct integers `candidates` and a target integer `target`, return all unique combinations of `candidates` where the chosen numbers sum up to `target`. You may use an element from `candidates` as many times as needed. The solution set must not contain duplicate combinations.

### Example

Let’s consider the following example for better understanding:

• Input: `candidates = [2, 3, 6, 7]`, `target = 7`
• Output: `[[2, 2, 3], [7]]`

In this example, the combinations that sum to 7 are `[2, 2, 3]` and `[7]`.

## Intuition Behind the Solution

To tackle the Combination Sum I problem, we can utilize a backtracking approach. The intuition here is to explore all possible combinations of numbers that may lead us to the target sum. The backtracking algorithm will allow us to build combinations incrementally and backtrack whenever we exceed the target.

### Steps Involved:

1. Start with an empty combination: We’ll begin with an empty combination and a target sum to reach.
2. Iterate through the candidates: For each candidate, we can either include it in our combination or skip it.
3. Recursive exploration: If we include a candidate, we will continue exploring with the same candidate (since we can reuse it) and a reduced target.
4. Check for completion: If our current combination sums to the target, we add it to our results.
5. Backtrack: If the current sum exceeds the target, we backtrack to explore other combinations.

## Code Solution

Now, let’s translate our thought process into code. Below is a Python implementation using backtracking:

``````def combination_sum(candidates, target):
def backtrack(start, path, target):
# Base case: if target is achieved
if target == 0:
result.append(path)
return
# Iterate over the candidates
for i in range(start, len(candidates)):
# If the candidate exceeds the target, break the loop
if candidates[i] > target:
break
# Include the candidate in the path and continue
backtrack(i, path + [candidates[i]], target - candidates[i])

candidates.sort()  # Sort candidates to facilitate early stopping
result = []
backtrack(0, [], target)
return result

# Example usage
candidates = [2, 3, 6, 7]
target = 7
print(combination_sum(candidates, target))
``````

### Explanation of the Code:

• We define a helper function `backtrack` that takes the current starting index, the current path of numbers, and the remaining target.
• We check if the `target` is zero, indicating a valid combination, and store it in our results.
• We loop through the `candidates` starting from the current index, checking if adding a candidate would surpass the target.
• If it doesn’t, we recursively call `backtrack` with the updated path and reduced target.

## Conclusion

The Combination Sum I problem beautifully demonstrates the power of backtracking in finding all possible combinations that meet a certain criterion. By carefully managing the state and employing recursion, we can explore a vast search space efficiently.

Feel free to test the code with different inputs and explore how the backtracking algorithm adapts to various scenarios. Happy coding!