Combination Sum

Explanation & Solution

Description

Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order.

The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different.

The test cases are generated such that the number of unique combinations that sum up to target is less than 150 combinations for the given input.

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

Output: [[2,2,3],[7]]

Explanation: 2 + 2 + 3 = 7 and 7 = 7. These are the only two combinations.

Constraints

1 <= candidates.length <= 30
2 <= candidates[i] <= 40
All elements of candidates are distinct
1 <= target <= 40

Approach

Subsets pattern

1. Sort the Candidates

Sort candidates in ascending order
This allows us to prune branches early: if candidates[i] > remaining, all subsequent candidates are also too large, so we can break

2. Initialize Backtracking

Create an empty result array to collect valid combinations
Start the recursive backtrack function with start = 0, remaining = target, and an empty path

3. Base Case — Found a Valid Combination

If remaining === 0, the current path sums exactly to target
Push a copy of path into result and return

4. Recursive Exploration

Loop from index start to the end of candidates
If candidates[i] > remaining, break out of the loop (pruning)
Otherwise, add candidates[i] to path and recurse with the same index i (allowing reuse of the same number)
After recursion, remove the last element from path (backtrack)

5. Why Start Index Prevents Duplicates

By only considering candidates from index start onward, we ensure combinations are built in non-decreasing order
This means [2,3] is generated but [3,2] is not, avoiding duplicate combinations

Key Insight

The start index is the key to avoiding duplicate combinations: each recursive call only looks at candidates at or after the current index, ensuring each unique combination is generated exactly once
Sorting enables early termination: once a candidate exceeds the remaining target, all larger candidates can be skipped

Time

**O(N^(T/M))** where N is the number of candidates, T is the target, and M is the minimum candidate value

Space

O(T/M) for the recursion depth

Visualization

Input:

Backtracking Exploration

current path

empty

No animation available

ExploringFoundBacktrack

0 steps

Solution Code

Combinations

Combination Sum II