# 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`.

`#mermaid-svg-AJnNdnWmqR5Q8JoH{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#000000;}#mermaid-svg-AJnNdnWmqR5Q8JoH .error-icon{fill:#552222;}#mermaid-svg-AJnNdnWmqR5Q8JoH .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-AJnNdnWmqR5Q8JoH .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-AJnNdnWmqR5Q8JoH .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-AJnNdnWmqR5Q8JoH .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-AJnNdnWmqR5Q8JoH .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-AJnNdnWmqR5Q8JoH .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-AJnNdnWmqR5Q8JoH .marker{fill:#666;stroke:#666;}#mermaid-svg-AJnNdnWmqR5Q8JoH .marker.cross{stroke:#666;}#mermaid-svg-AJnNdnWmqR5Q8JoH svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-AJnNdnWmqR5Q8JoH .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#000000;}#mermaid-svg-AJnNdnWmqR5Q8JoH .cluster-label text{fill:#333;}#mermaid-svg-AJnNdnWmqR5Q8JoH .cluster-label span{color:#333;}#mermaid-svg-AJnNdnWmqR5Q8JoH .label text,#mermaid-svg-AJnNdnWmqR5Q8JoH span{fill:#000000;color:#000000;}#mermaid-svg-AJnNdnWmqR5Q8JoH .node rect,#mermaid-svg-AJnNdnWmqR5Q8JoH .node circle,#mermaid-svg-AJnNdnWmqR5Q8JoH .node ellipse,#mermaid-svg-AJnNdnWmqR5Q8JoH .node polygon,#mermaid-svg-AJnNdnWmqR5Q8JoH .node path{fill:#eee;stroke:#999;stroke-width:1px;}#mermaid-svg-AJnNdnWmqR5Q8JoH .node .label{text-align:center;}#mermaid-svg-AJnNdnWmqR5Q8JoH .node.clickable{cursor:pointer;}#mermaid-svg-AJnNdnWmqR5Q8JoH .arrowheadPath{fill:#333333;}#mermaid-svg-AJnNdnWmqR5Q8JoH .edgePath .path{stroke:#666;stroke-width:1.5px;}#mermaid-svg-AJnNdnWmqR5Q8JoH .flowchart-link{stroke:#666;fill:none;}#mermaid-svg-AJnNdnWmqR5Q8JoH .edgeLabel{background-color:white;text-align:center;}#mermaid-svg-AJnNdnWmqR5Q8JoH .edgeLabel rect{opacity:0.5;background-color:white;fill:white;}#mermaid-svg-AJnNdnWmqR5Q8JoH .cluster rect{fill:hsl(210,66.6666666667%,95%);stroke:#26a;stroke-width:1px;}#mermaid-svg-AJnNdnWmqR5Q8JoH .cluster text{fill:#333;}#mermaid-svg-AJnNdnWmqR5Q8JoH .cluster span{color:#333;}#mermaid-svg-AJnNdnWmqR5Q8JoH div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:12px;background:hsl(-160,0%,93.3333333333%);border:1px solid #26a;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-AJnNdnWmqR5Q8JoH:root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;}#mermaid-svg-AJnNdnWmqR5Q8JoH flowchart{fill:apa;}Start: [] (5)Include 2: [2] (3)Include 3: [3] (2)Include 2: [2, 2] (1)Include 3: [2, 3] (0)Include 3: [3, 3] (-1)Include 2: [2, 2, 2] (-1)Target Reached: [2, 3]`

### Explanation of the tree

• Root Node `A` (“Start: [] (5)”): Start with an empty combination and a target of `5`.
• Node `B1` (“Include 2: [2] (3)”): Include `2` in the combination, reducing the target to `3`.
• Node `C1` (“Include 2: [2, 2] (1)”): Include another `2`, reducing the target to `1`.
• Node `D1` (“Include 2: [2, 2, 2] (-1)”): Including another `2` would exceed the target (`-1`), so we backtrack.
• Node `C2` (“Include 3: [2, 3] (0)”): Including `3` after `2` makes the combination `[2, 3]` reach the target of `5`.
• Node `B2` (“Include 3: [3] (2)”): Include `3` in the combination initially, reducing the target to `2`.
• Node `C3` (“Include 3: [3, 3] (-1)”): Including another `3` would exceed the target (`-1`), so we backtrack.
• Leaf Node (`Target Reached: [2, 3]`): Represents the valid combination `[2, 3]` that sums to `5`.

### Key Points to Remember:

1. Recursive Exploration: Explore all combinations by including and excluding candidates.
2. Backtracking: Remove the last element to explore another path once a path is either successful or fails.
3. Efficiency: Only explore candidates in non-descending order by maintaining a `start` index, avoiding duplicate combinations.
No Comment