Problem

https://leetcode.com/problems/combination-sum

What is the Problem?

1. You are given a list of integers candidates.
2. You are also given an integer target.
3. Each number in candidates can be reused any number of times.
4. Return all unique combinations of numbers that sum up to target.

Approach

1. Use a recursive approach with backtracking (similar to BFS) to explore all possible combinations.
2. The base case of the recursion is when the sum of the current combination equals the target.
3. To avoid redundant computations and duplicate combinations, sort the list first and only consider the current or later candidates in recursive calls.

Solution

def combinationSum(candidates: List[int], target: int) -> List[List[int]]:
    
    combinations = []
    def helper(index, target, selected):

        if target == 0:
            return selected

        for idx in range(index, len(candidates)):
            candidate = candidates[idx]
            if target - candidate >= 0:
                combination = helper(idx, target - candidate, selected + [candidate])
                if combination and combination not in combinations:
                    combinations.append(combination)
    
    helper(0, target, [])
    return combinations

assert combinationSum([2,3,6,7], 7) == [[2,2,3],[7]]

Key Concepts

• Recursive exploration: We explore all paths by repeatedly subtracting from the target.
• Backtracking: We track the current path (selected) and backtrack when necessary.
• Avoiding duplicates: By always iterating from the current index (index), we prevent combinations with the same elements in different orders.

Time Complexity

Let T be the target and N be the number of candidates. In the worst case, the time complexity is exponential, approximately O(N^T), due to the branching factor of the recursive calls. Sorting the candidates first and pruning paths early can significantly reduce redundant computations.