Combination Sum

TIP103 Unit 8 Session 2 (Click for link to problem statements)

Problem Highlights

💡 Difficulty: Medium
⏰ Time to complete: 25-35 mins
🛠️ Topics: Backtracking, Recursion, Arrays

1: U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

Established a set (2-3) of test cases to verify their own solution later.

Established a set (1-2) of edge cases to verify their solution handles complexities.

Have fully understood the problem and have no clarifying questions.

Have you verified any Time/Space Constraints for this problem?

Can the same candidate be used more than once in a combination?
- Yes, each candidate may be chosen an unlimited number of times.
What makes two combinations the same?
- Two combinations are the same if they use the same numbers the same number of times, regardless of order. So [2, 2, 3] and [3, 2, 2] count as one combination, and the result should include it only once.
What should we return if no combination of candidates sums to target?
- An empty list, since there are no valid combinations.

HAPPY CASE
Input: candidates = [2, 3, 6, 7], target = 7
Output: [[2, 2, 3], [7]]
Explanation: 2 + 2 + 3 = 7 (note that 2 is used twice) and 7 = 7. These are the only unique combinations that sum to 7.

EDGE CASE
Input: candidates = [2], target = 1
Output: []
Explanation: The smallest candidate is larger than the target, so no combination can sum to 1.

2: M-atch

Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.

For Combination/Subset Generation Problems, we can consider the following approaches:

Backtracking: Build combinations one candidate at a time, recursing while the remaining target is positive and undoing (popping) each choice before trying the next.
Recursion with an Include/Exclude Decision Tree: At each candidate, decide whether to include it (possibly again) or move past it, which naturally avoids duplicate combinations.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea:
Use backtracking to explore all ways of spending the target. At each step, track the remaining amount and a start index into candidates. We may reuse the candidate at the current index (so unlimited repeats are allowed), but we never revisit earlier indices — this guarantees combinations are generated in a canonical order, so no duplicates like [2, 2, 3] and [3, 2, 2] appear. When the remaining amount hits 0, record a copy of the current combination.

1) Initialize an empty `combinations` list to collect results.
2) Define a helper backtrack(start, remaining, current):
   a) If `remaining` is 0, append a copy of `current` to `combinations` and return.
   b) For each index i from `start` to the end of candidates:
      i)   If candidates[i] > remaining, skip it (it would overshoot the target).
      ii)  Append candidates[i] to `current`.
      iii) Recurse with backtrack(i, remaining - candidates[i], current).
           Passing `i` (not i + 1) allows reusing the same candidate.
      iv)  Pop candidates[i] off `current` to undo the choice.
3) Call backtrack(0, target, []).
4) Return `combinations`.

⚠️ Common Mistakes

Recursing with i + 1 instead of i, which forbids reusing a candidate and misses combinations like [2, 2, 3].
Recursing with start = 0 every time, which generates duplicate combinations in different orders.
Appending current itself instead of a copy (current[:]), so later pops mutate the recorded answer.
Forgetting to stop recursing when the remaining amount goes negative, causing infinite recursion.

4: I-mplement

Implement the code to solve the algorithm.

def combination_sum(candidates, target):
    combinations = []

    def backtrack(start, remaining, current):
        # Base case: the current combination sums exactly to target
        if remaining == 0:
            combinations.append(current[:])  # Record a copy of the combination
            return
        # Try each candidate from `start` onward (never look backward)
        for i in range(start, len(candidates)):
            candidate = candidates[i]
            if candidate > remaining:
                continue  # This candidate would overshoot the target
            current.append(candidate)  # Choose the candidate
            backtrack(i, remaining - candidate, current)  # Pass i, not i + 1, to allow reuse
            current.pop()  # Undo the choice before trying the next candidate

    backtrack(0, target, [])
    return combinations

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code’s variables along the way.

Input: candidates = [2, 3, 6, 7], target = 7
- Start at index 0: choose 2 (remaining 5), choose 2 again (remaining 3), choose 3 (remaining 0) → record [2, 2, 3].
- Backtrack: further picks from [2, 2, 3, ...] and [2, 3, ...] overshoot, so those branches die out.
- Choosing 3 first leaves remaining 4, which no combination of {3, 6, 7} can hit; choosing 6 leaves remaining 1, a dead end.
- Choose 7 (remaining 0) → record [7].
- Output: [[2, 2, 3], [7]]
Input: candidates = [2], target = 1
- The only candidate 2 overshoots the remaining amount 1, so the loop records nothing.
- Output: []

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Assume N is the number of candidates, T is the target value, and M is the smallest candidate.

Time Complexity: O(N^(T/M)) because the recursion tree branches up to N ways at each level and can go T/M levels deep before the remaining amount is exhausted.
Space Complexity: O(T/M) for the recursion stack and the current combination being built (excluding the space for the output list).