# Combination sum leetcode

**Problem Statement:**

Given a list of distinct integers `candidates`

and a target integer `target`

, find all unique combinations where the chosen numbers sum up to the target. Each number in `candidates`

can be used an unlimited number of times.

**Example:**

**Input:**`candidates = [2, 3]`

,`target = 5`

**Output:**`[[2, 3]]`

**Explanation:**

- We can use
`2`

once and`3`

once to get`5`

(i.e.,`[2, 3]`

). - No other combinations sum up to
`5`

.

**Approach: Backtracking**

The backtracking approach will help us explore all possible combinations recursively. At each recursive call, we will choose to include a candidate or move to the next one.

**Combination Sum Code in JavaScript (Smaller Example):**

```
function combinationSum(candidates, target) {
const result = [];
function backtrack(remaining, combination, start) {
if (remaining === 0) {
result.push([...combination]);
return;
}
if (remaining < 0) return;
for (let i = start; i < candidates.length; i++) {
combination.push(candidates[i]);
backtrack(remaining - candidates[i], combination, i); // Include the same element again
combination.pop(); // Backtrack
}
}
backtrack(target, [], 0);
return result;
}
// Example Usage
console.log(combinationSum([2, 3], 5)); // Output: [[2, 3]]`
```

**Explanation of Code:**

- We use a
**recursive backtracking function**to explore all combinations. - The recursive function includes or skips the current candidate and continues exploring until the target is achieved or surpassed.

### Recursive State Tree:

The diagram below represents the recursive state tree for `candidates = [2, 3]`

and `target = 5`

.

### Explanation of the tree

**Root Node**: Start with an empty combination and a target of`A`

(“Start: [] (5)”)`5`

.**Node**: Include`B1`

(“Include 2: [2] (3)”)`2`

in the combination, reducing the target to`3`

.**Node**: Include another`C1`

(“Include 2: [2, 2] (1)”)`2`

, reducing the target to`1`

.**Node**: Including another`D1`

(“Include 2: [2, 2, 2] (-1)”)`2`

would exceed the target (`-1`

), so we backtrack.**Node**: Including`C2`

(“Include 3: [2, 3] (0)”)`3`

after`2`

makes the combination`[2, 3]`

reach the target of`5`

.**Node**: Include`B2`

(“Include 3: [3] (2)”)`3`

in the combination initially, reducing the target to`2`

.**Node**: Including another`C3`

(“Include 3: [3, 3] (-1)”)`3`

would exceed the target (`-1`

), so we backtrack.**Leaf Node (**: Represents the valid combination`Target Reached: [2, 3]`

)`[2, 3]`

that sums to`5`

.

**Key Points to Remember:**

**Recursive Exploration:**Explore all combinations by including and excluding candidates.**Backtracking:**Remove the last element to explore another path once a path is either successful or fails.**Efficiency:**Only explore candidates in non-descending order by maintaining a`start`

index, avoiding duplicate combinations.