LeetCode Solutions Blog

Combination Sum

Number: 39

Difficulty: Medium

Paid? No

Problem Description

Given an array of distinct integers and a target, return all unique combinations from the array where the chosen numbers sum to the target. Each number in the array can be used an unlimited number of times. The solution set must not contain duplicate combinations.

Key Insights

Backtracking is a natural fit to explore all potential combinations.
Sorting candidates simplifies the process by allowing early termination if the current candidate exceeds the remaining target.
Recursion is used to build combinations and backtrack once the current path exceeds or meets the target.
The same candidate can be reused in the combination, so the recursive call does not advance the index.

Space and Time Complexity

Time Complexity: O(2^(target/min(candidates))) in the worst case where many combinations are possible. Space Complexity: O(target/min(candidates)) for the recursion stack and temporary space used to store combinations.

Solution

The solution uses a backtracking approach. First, sort the candidates to enable pruning of recursive calls once the candidate exceeds the remaining target. A recursive helper function builds up a combination, subtracting the candidate value from the target until it reaches zero (a valid combination) or becomes negative (an invalid path). The recursion allows the same candidate to be chosen again. Each valid combination is then added to the result list.

Code Solutions

# Function to find all unique combinations that sum to the target
def combinationSum(candidates, target):
    # List to store all valid combinations
    result = []
    # Sort candidates to facilitate pruning of the search
    candidates.sort()
    
    # Recursive helper function for backtracking
    def backtrack(remaining, start, path):
        # If remaining is 0, path is a valid combination so add a copy of it to result
        if remaining == 0:
            result.append(list(path))
            return
        # Loop through candidates starting from the current index
        for i in range(start, len(candidates)):
            # If candidate is greater than remaining, break out for efficiency
            if candidates[i] > remaining:
                break
            # Include candidate in the current combination path
            path.append(candidates[i])
            # Recursively call backtrack with updated remaining and same index (allowing reuse)
            backtrack(remaining - candidates[i], i, path)
            # Backtrack by removing the candidate added in this iteration
            path.pop()
    
    # Start backtracking from index 0 with an empty path
    backtrack(target, 0, [])
    return result

# Example usage
print(combinationSum([2,3,6,7], 7))