Leetcode 39: Combination Sum

1. Problem Statement (Simple Explanation):

You are given:

An array of distinct positive integers candidates.
A positive integer target.

You must find all unique combinations of numbers from candidates such that:

The sum of the chosen numbers equals target.
You can use the same number unlimited times.
Two combinations are considered different if the count of at least one number differs.
Return all combinations (order of combinations and order inside each combination does not matter).

The number of unique combinations is guaranteed to be < 150.

2. Examples:

Example 1:

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

Valid combinations:

2 + 2 + 3 = 7 → [2,2,3]
7 = 7 → [7]

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

Example 2:

Input: candidates = [2,3,5], target = 8

Valid combinations:

2 + 2 + 2 + 2 = 8 → [2,2,2,2]
2 + 3 + 3 = 8 → [2,3,3]
3 + 5 = 8 → [3,5]

Output: [[2,2,2,2],[2,3,3],[3,5]]

Example 3:

Input: candidates = [2], target = 1

No combination sums to 1.

Output: []

3. Approach – Backtracking (DFS) with Reuse Allowed:

This is a classic backtracking / DFS combination problem.

Intuition:

We explore combinations by:

Maintaining:

start index in candidates (to prevent permutation duplicates).
current list of chosen numbers.
remaining sum (initially target).

For each index i starting from start:

Option to include candidates[i]:

Add it to current.
Recurse with:

start = i (not i+1, because we can reuse the same number).
remaining = remaining - candidates[i].

Stop if remaining < 0 (over target).
If remaining == 0 → we found a valid combination; add a copy of current to the result.

We never go backwards in indices (we pass i as next start, not 0), which ensures combinations are generated in non-decreasing order of indices and no duplicates.

Algorithm (Step-by-Step):

Optionally sort candidates (not required for correctness here, but can help pruning).
Create an empty list result to collect valid combinations.
Define backtrack(start, remaining, current):

If remaining == 0:

Add a copy of current to result; return.

If remaining < 0:

Return (invalid path).

For i from start to len(candidates)-1:

Let num = candidates[i].
Append num to current.
Call backtrack(i, remaining - num, current) (note i, not i+1, because unlimited uses).
Remove last element from current (backtrack).