Combination Sum in Python

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        def backtrack(start, combination, total):
            # Base case: if the total equals target, add the current combination to the result
            if total == target:
                result.append(list(combination))
                return

            # Explore further by trying each candidate
            for i in range(start, len(candidates)):
                # If the current candidate exceeds the remaining sum, skip it
                if total + candidates[i] > target:
                    continue
                # Add the candidate to the current combination
                combination.append(candidates[i])
                # Recursively explore further with the updated combination and total
                backtrack(i, combination, total + candidates[i])
                # Backtrack by removing the last element before moving to the next candidate
                combination.pop()

        # Initialize the result list
        result = []
        # Start the recursive exploration
        backtrack(0, [], 0)
        return result

Next