Problem: Combination Sum

Problem Statement

Given an array of distinct integers candidates and a target, return a list of all unique combinations where the numbers sum to target. You may use the same number an unlimited number of times.

Approach: Backtracking with Pruning

Because we can reuse numbers, our decision tree doesn't shrink in width, but it must shrink in remaining target.

1. State: Current path, current sum, and starting index (to avoid duplicate combinations like [2,3] and [3,2]).
2. Base Case:
   • sum == target: Success! Add to results.
   • sum > target: Fail! Stop exploring this branch (Pruning).
3. Recursion: Start the loop from index to allow reusing the current number but prevent using previous numbers.

Java Implementation

public List<List<Integer>> combinationSum(int[] candidates, int target) {
    List<List<Integer>> results = new ArrayList<>();
    backtrack(results, new ArrayList<>(), candidates, target, 0);
    return results;
}

private void backtrack(List<List<Integer>> res, List<Integer> path, int[] nums, int remain, int start) {
    if (remain < 0) return; // Pruning
    if (remain == 0) {
        res.add(new ArrayList<>(path));
        return;
    }
    
    for (int i = start; i < nums.length; i++) {
        path.add(nums[i]);
        // We pass 'i' as start index because we can reuse the same element
        backtrack(res, path, nums, remain - nums[i], i);
        path.remove(path.size() - 1);
    }
}

Complexity Analysis

• Time Complexity: $O(N^{\frac{T}{M} + 1})$ where $N$ is candidates, $T$ is target, and $M$ is the smallest candidate.
• Space Complexity: $O(\frac{T}{M})$ for the recursion stack.

Interview Tips

• Why pass i as the next start? "To ensure we only move forward in the array, preventing duplicate combinations in different orders."
• Mention sorting the array first to prune even earlier (if remain - nums[i] < 0, the rest of the loop can be skipped).