LeetCode 39: Combination Sum — Step-by-Step Visual Trace

#leetcode #python #algorithms

Medium — Backtracking | Array | Recursion

The Problem

Find all unique combinations of candidates where the candidate numbers sum to target, where each number may be used multiple times.

Approach

Uses backtracking to explore all possible combinations by recursively adding candidates to the current combination and backtracking when the target is exceeded or reached. The start index prevents duplicate combinations by ensuring we only consider candidates at or after the current position.

Time: O(N^(T/M)) · Space: O(T/M)

Code

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        def backtrack(start, target, combination):
            if target == 0:
                result.append(
                    combination[:]
                )  # Append a copy of the current combination
                return

            for i in range(start, len(candidates)):
                if candidates[i] > target:
                    continue  # Skip if the candidate is too large

                combination.append(candidates[i])
                backtrack(i, target - candidates[i], combination)
                combination.pop()  # Backtrack

        result = []
        backtrack(0, target, [])
        return result