Combination Sum medium

Problem Statement

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.

It's guaranteed that the number of unique combinations is less than 150.

Example 1

Input: candidates = [2,3,6,7], target = 7 Output: [[2,2,3],[7]] Explanation: 2 and 3 are candidates. 2 + 2 + 3 = 7. 7 is a candidate, 7 = 7.

Example 2

Input: candidates = [2,3,5], target = 8 Output: [[2,2,2,2],[2,3,3],[3,5]] Explanation: 2,3 and 5 are candidates. 2 + 2 + 2 + 2 = 8 2 + 3 + 3 = 8 3 + 5 = 8

Steps

1. Sort the candidates: Sorting allows us to efficiently prune the search space. We can stop exploring branches if the current sum exceeds the target.

2. Backtracking Algorithm: Use a recursive backtracking approach.

   • At each step, we have a current combination and a remaining target sum.
   • We iterate through the candidates. For each candidate:
     • If the candidate is less than or equal to the remaining target:
       • Add the candidate to the current combination.
       • Recursively call the function with the updated combination and remaining target.
       • Remove the candidate from the current combination (backtracking step). This is crucial for exploring other possibilities.
     • If the candidate is greater than the remaining target, we can skip it since it can't contribute to a valid combination.

3. Base Cases:

   • If the remaining target is 0, we've found a valid combination, so add it to the result list.
   • If the remaining target is negative, the current branch is invalid, so we don't proceed further.

4. Handle Duplicates: The problem statement guarantees unique combinations. While the candidates array is distinct, we don't need extra handling to prevent duplicate combinations because the sorting and backtracking ensures that we only find unique combinations.

Explanation

The backtracking algorithm systematically explores all possible combinations. Sorting the candidates allows us to optimize the search. When we add a candidate to the combination, we recursively explore the possibilities with that candidate. If it leads to a valid combination, we add it to the result. Then, we backtrack and remove the candidate to explore other possibilities. This ensures that we consider all valid combinations without duplicates.

Code

function combinationSum(candidates: number[], target: number): number[][] {
    const result: number[][] = [];
    candidates.sort((a, b) => a - b); // Sort candidates for efficiency

    function backtrack(combination: number[], remaining: number, start: number) {
        if (remaining === 0) {
            result.push([...combination]); // Found a valid combination
            return;
        }

        if (remaining < 0) {
            return; // Current branch is invalid
        }

        for (let i = start; i < candidates.length; i++) {
            combination.push(candidates[i]);
            backtrack(combination, remaining - candidates[i], i); // Explore with current candidate
            combination.pop(); // Backtrack: remove the candidate for other possibilities
        }
    }

    backtrack([], target, 0);
    return result;
}

Complexity

• Time Complexity: O(N^T), where N is the number of candidates and T is the target value. In the worst case, we might explore all possible combinations.
• Space Complexity: O(T) in the worst case, due to the recursive call stack. The space used for storing the result is O(K * T), where K is the average length of combinations, although K is typically much smaller than T. In practice, the space complexity is dominated by the recursive call stack.