39. Combination Sum

Problem Description

Given a set of distinct positive integers candidates and a target integer target, find all unique combinations in candidates where the chosen numbers sum to target. Each number in candidates may be chosen an unlimited number of times.

Approach: Backtracking with Pruning

The most efficient approach is backtracking, enhanced with pruning to avoid unnecessary computations.

1. Sorting: Sort the candidates array. This allows for efficient pruning because if the current sum exceeds the target, we can stop exploring further combinations involving larger numbers.

2. Backtracking Function: The core logic lies in a recursive backtracking function. This function takes:

   • index: The current index in the candidates array.
   • remainingSum: The remaining sum needed to reach the target.
   • combination: The current combination being built.
   • result: A list to store all valid combinations.

3. Base Cases:

   • If remainingSum is 0, a valid combination is found, so add combination to result.
   • If remainingSum is negative or index is out of bounds, this branch is invalid, so return.

4. Recursive Step: For each element at the current index, explore two possibilities:

   • Include: Add the element to combination, recursively call the backtracking function with the updated remainingSum and the same index (allowing the same element to be chosen multiple times), and then remove the element from combination (backtracking).
   • Exclude: Recursively call the backtracking function with the same remainingSum and the next index (moving to the next element).

5. Initial Call: The backtracking function is initially called with index = 0, remainingSum = target, an empty combination, and an empty result list.

Time and Space Complexity

• Time Complexity: O(N * 2T), where N is the length of candidates and T is the target. In the worst case, each number might be included or excluded in every combination. However, the sorting and pruning significantly reduce the actual runtime in many cases.

• Space Complexity: O(T) in the worst case, due to the maximum depth of the recursion stack and the space required to store the largest possible combination.

Code Implementation (Python)

def combinationSum(candidates, target):
    result = []
    candidates.sort()  # Sort for efficient pruning
 
    def backtrack(index, remainingSum, combination):
        if remainingSum == 0:
            result.append(combination.copy())  # Found a valid combination
            return
        if remainingSum < 0 or index >= len(candidates):
            return  # Invalid branch
 
        # Include the current element
        combination.append(candidates[index])
        backtrack(index, remainingSum - candidates[index], combination)
        combination.pop()  # Backtrack
 
        # Exclude the current element
        backtrack(index + 1, remainingSum, combination)
 
    backtrack(0, target, [])
    return result
 

The implementations in other languages (Java, C++, Go, TypeScript, Rust, C#, PHP) will follow a very similar structure, differing only in syntax and data structure specifics. The core backtracking algorithm remains the same.