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