💬 Discord
Sign In
NeetCode #489LC-39MediumBacktrackingBlind 75NC 150NC 250
← Back to All Problems

#489 · #39 · Combination Sum(组合总和)

📌 Problem Statement & Constraints

Given an array of distinct integers candidates and a target, return all unique combinations that sum to the target. Each candidate may be used unlimited times. Constraints: 1 <= candidates.length <= 30, 2 <= candidates[i] <= 40, 1 <= target <= 40.

💡 Core Algorithmic Approaches

  1. Backtrack with two decisions per index: skip it, or take it and stay at the same index (allowing reuse).
  2. Staying at the same index is what enables unlimited reuse.
  3. Prune when the remaining target goes negative.
  4. Because the candidates are distinct, no deduplication is needed.

💻 Benchmark Python3 Implementation

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

        def dfs(i: int, path: List[int], remain: int) -> None:
            if remain == 0:
                res.append(path[:])        # a valid combination
                return
            if i == len(candidates) or remain < 0:
                return
            dfs(i + 1, path, remain)       # skip candidates[i]
            path.append(candidates[i])
            dfs(i, path, remain - candidates[i])   # reuse candidates[i]
            path.pop()

        dfs(0, [], target)
        return res


# Loop-based formulation: only move forward, so combinations are naturally unique
class Solution2:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        res = []

        def dfs(start: int, path: List[int], remain: int) -> None:
            if remain == 0:
                res.append(path[:])
                return
            for i in range(start, len(candidates)):
                if candidates[i] > remain:
                    continue               # prune (valid only after sorting)
                path.append(candidates[i])
                dfs(i, path, remain - candidates[i])   # i, not i+1 -> reuse
                path.pop()

        candidates.sort()
        dfs(0, [], target)
        return res

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n^(target/min)) in the worst case, bounded by the number of valid combinations.
💾 Space Complexity
O(target/min) for the recursion depth.

⚠️ Interview Pitfalls & Follow-ups

  • Advancing to i + 1 when taking a candidate: reuse would be impossible.
  • Not pruning on remain < 0: the recursion would explore useless branches (and loop forever if no candidate is positive).
  • Using a set of sorted tuples for deduplication: unnecessary since the candidates are distinct and the loop only moves forward.
  • Forgetting path.pop(): the path would accumulate across branches.