Coding Interview Questions | Combination Sum

January 23rd, 2024

Combination Sum Problem Introduction:

This summary will talk about my solution to the combination sum problem as seen on leetcode here. A synopsis of the problem summary will be shown below:

Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order.

The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the
frequency of at least one of the chosen numbers is different.

The test cases are generated such that the number of unique combinations that sum up to target is less than 150 combinations for the given input.

How do you solve the Combination Sum Problem using Dynamic Programming?

Solution:

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

  const backtrack = (startIndex: number, remainingTarget: number) => {
    if (remainingTarget === 0) {
      // Base case: combination found
      result.push([...currentCombination]);
      return;
    }

    for (let i = startIndex; i < candidates.length; i++) {
      const candidate = candidates[i];

      if (candidate <= remainingTarget) {
        // Include the candidate in the current combination
        currentCombination.push(candidate);

        // Continue exploration with the same candidate (allowing duplicates)
        backtrack(i, remainingTarget - candidate);

        // Backtrack: remove the candidate for the next iteration
        currentCombination.pop();
      }
    }
  };

  // Start the backtracking process
  backtrack(0, target);

  return result;
}

Combination Sum Solution Summary:

Below is a breakdown of the key aspects of the solution above for the combination sum problem:

1. Backtracking Approach: The algorithm employs a backtracking approach to explore all possible combinations of candidates that sum up to the target.

2. Recursive Backtrack Function: The backtrack function is the core of the algorithm, taking parameters startIndex and remainingTarget. It explores combinations starting from the given index and considers the remaining target.

3. Base Case Handling: The base case checks if remainingTarget is 0, indicating that a valid combination is found. In such cases, the current combination is added to the result.

4. Iteration through Candidates: The algorithm iterates through the candidates array, considering each candidate as a potential element in the combination.

5. Duplicate Combinations: The algorithm allows duplicates in the combinations, ensuring that each candidate can be chosen an unlimited number of times.

Complexities

1. Time Complexity: The time complexity is influenced by the number of recursive calls made by the backtracking function. In the worst case, where all combinations are valid, the time complexity is exponential, denoted as O(2^n), where n is the length of the candidates array.

2. Space Complexity: The space complexity is determined by the recursive call stack during the backtracking process. In the worst case, it is also exponential, O(2^n).