Combination Sum - Python Solution

1. Introduction

The "Combination Sum" problem is a classic example of a combination-based question often seen in coding interviews and competitive programming. It involves finding all unique combinations of numbers in an array that add up to a given target sum. This problem tests one's ability to implement an effective backtracking approach to explore all potential combinations.

Problem

Given an array of distinct integers candidates and a target integer target, the task is to return a list of all unique combinations of candidates where the chosen numbers sum to target. 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.

2. Solution Steps

1. Sort the candidates array to help with optimizations.

2. Use a backtracking approach to explore all possible combinations.

3. Track the current combination and the sum of its elements.

4. Backtrack when the sum exceeds the target or when all possibilities have been explored.

5. Add the combination to the result when the sum equals the target.

3. Code Program

def combinationSum(candidates, target):
    # Function to perform backtracking
    def backtrack(start, combination, total):
        # Base case: when the total equals the target
        if total == target:
            results.append(list(combination))
            return
        # Explore further only if total is less than target
        for i in range(start, len(candidates)):
            if total + candidates[i] > target:
                continue
            combination.append(candidates[i])
            backtrack(i, combination, total + candidates[i])
            combination.pop()  # backtrack

    results = []
    candidates.sort()  # Sort the candidates
    backtrack(0, [], 0)
    return results

# Testing the function with an example
print(combinationSum([2,3,6,7], 7))

Output:

[[2, 2, 3], [7]]

Explanation:

1. Sorting: The candidates array is first sorted. This helps to optimize the backtracking process.

2. Backtracking Function: The backtrack function explores combinations, starting from a given index.

3. Base Case: If the sum of elements in the current combination equals the target, the combination is added to the results.

4. Recursive Exploration: The function recursively explores each candidate by adding it to the current combination and then calls itself with the updated total.

5. Backtracking: After exploring with a candidate, it is removed (backtracked), and the function proceeds to the next candidate.

6. Results: The function returns all unique combinations that sum up to the target.