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, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times. 7 is a candidate, and 7 = 7. These are the only two combinations.

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. These are the only three combinations.

Steps

1. Sort the candidates: Sorting the candidates allows for efficient pruning of the search space.

2. Backtracking: Utilize a backtracking algorithm to explore all possible combinations. The backtracking function will recursively explore combinations, adding candidates and subtracting from the target until the target is reached or exceeded.

3. Pruning: If at any point the remaining target becomes negative, we can prune the search branch since adding more positive numbers will only increase the sum, never making it equal to the target.

4. Handling Duplicates: Since the same number can be chosen multiple times, we don't need to mark numbers as used. The natural recursive process of the backtracking algorithm handles this.

5. Store Results: Collect all valid combinations that sum to the target in a results list.

Explanation

The code employs a recursive backtracking approach. The backtrack function explores all possible combinations by recursively adding candidates. The base cases are:

• If the target becomes 0, it means a valid combination has been found, so it's added to the result.
• If the target becomes negative, it means the current combination exceeds the target, so the recursion stops.

For each candidate, the backtrack function recursively calls itself, adding the candidate to the current combination and reducing the target accordingly. This process continues until all possible combinations are explored. The sorting of candidates helps in efficient pruning; if the current candidate is already larger than the remaining target, there is no point in exploring further combinations that include this candidate.

Code

def combinationSum(candidates, target):
    """
    Finds all unique combinations of candidates that sum to target.

    Args:
        candidates: A list of distinct integers.
        target: The target sum.

    Returns:
        A list of lists, where each inner list represents a unique combination.
    """
    result = []
    candidates.sort()  # Sort for efficient pruning

    def backtrack(combination, remaining, start):
        if remaining == 0:
            result.append(combination.copy())
            return
        if remaining < 0:
            return

        for i in range(start, len(candidates)):
            combination.append(candidates[i])
            backtrack(combination, remaining - candidates[i], i)  # i, not i+1, allows duplicates
            combination.pop()  # Backtrack: remove the last added candidate

    backtrack([], target, 0)
    return result

Complexity

• Time Complexity: O(N^T), where N is the number of candidates and T is the target. In the worst case, we might explore all possible combinations. However, sorting improves this in practice.

• Space Complexity: O(T) in the worst case, due to the recursive call stack depth which is bounded by the target value. The space used for storing the result is also proportional to the number of combinations, which can be large in worst-case scenarios.