39. Combination Sum

combinationSum.py

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        solutions: List[List[int]] = []
        n: int = len(candidates)

        candidates.sort()  # Helps us to prune the search space (cf line 15)

        def backtrack(sum_: int, start_idx: int, cur_list: List[int]) -> None:
            if sum_ == target: # Goal - base case 
                solutions.append(cur_list)
                return

            for i in range(start_idx, n):
                if sum_ + candidates[i] <= target:
                    backtrack(sum_ + candidates[i], i, cur_list + [candidates[i]])  # Explore further the solution space 
                else:
                    return  # Pruning - no need to explore further if the sum is above the target value.

        backtrack(0, 0, [])
        return solutions