leetcode-39 Combination Sum

[39] Combination Sum

Key Concept: Backtracking with Reusable Elements - Similar to subsets, but elements can be reused. Use backtracking with a target that decreases as we add elements. Stop when target becomes 0 or negative.

Key difference from Subsets: Can reuse same element (pass same index in recursion instead of i+1).

# Given an array of distinct integers candidates and a target integer,
# return a list of all unique combinations 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.
#
# Example 1:
# Input: candidates = [2,3,6,7], target = 7
# Output: [[2,2,3],[7]]
#
# Example 2:
# Input: candidates = [2,3,5], target = 8
# Output: [[2,2,2,2],[2,3,3],[3,5]]
#
# Example 3:
# Input: candidates = [2], target = 1
# Output: []
#
# Constraints:
# 1 <= candidates.length <= 30
# 2 <= candidates[i] <= 40
# All elements of candidates are distinct.
# 1 <= target <= 40

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

        def backtrack(start, current_combination, remaining):
            # Base cases
            if remaining == 0:
                result.append(current_combination[:])  # Found a valid combination
                return
            if remaining < 0:
                return  # Exceeded target, backtrack

            # Try each candidate starting from start index
            for i in range(start, len(candidates)):
                current_combination.append(candidates[i])

                # Key: Pass i (not i+1) to allow reusing same element
                backtrack(i, current_combination, remaining - candidates[i])

                current_combination.pop()  # backtrack

        backtrack(0, [], target)
        return result

    # Optimized version with early termination
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        result = []
        candidates.sort()  # Sort to enable early termination

        def backtrack(start, current_combination, remaining):
            if remaining == 0:
                result.append(current_combination[:])
                return

            for i in range(start, len(candidates)):
                # Early termination: if current candidate > remaining, stop
                if candidates[i] > remaining:
                    break

                current_combination.append(candidates[i])
                backtrack(i, current_combination, remaining - candidates[i])
                current_combination.pop()

        backtrack(0, [], target)
        return result

# Time Complexity: O(n^(target/min)) in worst case
# Space Complexity: O(target/min) - recursion depth
#
# Key Insight: Pass same index to allow reusing elements
# Compare with Combination Sum II where each element used only once