Combination Sum

Explain the Problem

Given an array of distinct integers candidates and a target integer target, return all unique combinations of candidates where the chosen numbers sum to target. The same number may be chosen from candidates an unlimited number of times. The combinations may be returned in any order.

Example:

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

Output:

[
  [7],
  [2, 2, 3]
]

Short, Easy-to-Remember Solution/Approach

To solve this problem, we can use a recursive backtracking approach:

1. Recursive Function: We'll create a helper function that tries to build combinations by choosing each candidate repeatedly until the sum exceeds the target.

2. Backtracking: If the current combination's sum equals the target, we add it to the result list. If it exceeds the target, we backtrack.

Solution in JavaScript with Code Commenting

Here's the JavaScript solution with detailed comments:

function combinationSum(candidates, target) {
  const result = [];

  // Helper function for backtracking
  function backtrack(start, path, sum) {
    // If the current sum equals the target, add the path to the result
    if (sum === target) {
      result.push([...path]);
      return;
    }

    // If the current sum exceeds the target, backtrack
    if (sum > target) {
      return;
    }

    // Loop through the candidates starting from the current index
    for (let i = start; i < candidates.length; i++) {
      // Add the current candidate to the path
      path.push(candidates[i]);
      // Recursively try the next candidates with the updated sum
      backtrack(i, path, sum + candidates[i]);
      // Remove the last candidate from the path to backtrack
      path.pop();
    }
  }

  // Start the backtracking with an empty path and sum of 0
  backtrack(0, [], 0);

  return result;
}

Explanation of the Solution in Simple Terms

Imagine you have a box of coins, and each coin has a different value. You want to find all the ways to use these coins to make up a certain amount of money (the target).

• Recursive Function: This is like a helper that tries different combinations of coins to see which ones add up to the target.

• Backtracking: This means if the current combination of coins doesn't work (either because it adds up to more than the target or you've tried all coins), you go back and try a different combination.

For each coin, you either add it to your current combination or skip it and try the next coin. If you find a combination that adds up to the target, you save it. If not, you undo your last step and try something else.

Code Explanation in Pointers

1. Initialize Result Array: Create an empty array to store the valid combinations.

2. Define Backtracking Function: Create a recursive function to explore different combinations.

3. Base Case - Target Met: If the sum equals the target, add the current path to the result.

4. Base Case - Target Exceeded: If the sum exceeds the target, return and backtrack.

5. Loop Through Candidates: Try each candidate from the current index onwards.

6. Add to Path: Add the current candidate to the path.

7. Recursive Call: Call the function recursively with the updated sum.

8. Backtrack: Remove the last candidate from the path before trying the next one.

Complexity Analysis

• Time Complexity: O(2^T/M), where T is the target and M is the minimum value in the candidates. This is because we explore each combination.

• Space Complexity: O(T/M), due to the recursion stack and the path array.

---