Combination Sum | Leetcode 39 | Backtracking Approach

Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order.

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.

The test cases are generated such that the number of unique combinations that sum up to target is less than 150 combinations for the given input.

Here’s the [Problem Link] to begin with.

Example 1:

Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]
Explanation:
2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times.
7 is a candidate, and 7 = 7.
These are the only two combinations.

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

Solution: Backtracking Approach

Intuition

Think of this like making change for a specific amount using unlimited coins of certain denominations! You can use each coin type (candidate) as many times as you want. For each coin, you have two choices: take it (and you can take it again later) or skip to the next coin type. It’s like standing at a vending machine where you keep pressing the same button until you either reach your target amount or go over it. We use backtracking to explore all possible combinations, when we take a coin, we stay at the same position to allow taking it again, and when we skip, we move to the next coin type.

Detailed Approach

1. Recursive Function: Create a helper function that takes current index, running total, current subset, candidates array, target, and result list.
2. Base Cases:
   • If total equals target: we found a valid combination, add a copy to results.
   • If total exceeds target: this path won’t work, stop exploring.
   • If index reaches array length: no more candidates to try, stop.
3. Choice 1 – Include Current Candidate: Add the candidate to subset and total, but keep the same index (allowing reuse of the same number).
4. Backtrack: After exploring the “include” path, remove the candidate from subset to clean up.
5. Choice 2 – Skip Current Candidate: Move to the next index without adding the current candidate.
6. Start Recursion: Begin with index 0, total 0, and empty subset.
7. Collect Results: All valid combinations will be stored in the result list.

Code

class Solution:
    def solve(self, index, total, subset, nums, target, result):
        # Base case: If the running total matches the target, record the current subset
        if total == target:
            result.append(subset.copy())  # Add a copy to avoid future modifications
            return
        # Pruning: If the running total exceeds the target, stop this path
        elif total > target:
            return
        # Base case: If we have considered all candidates, terminate this branch
        if index >= len(nums):
            return

        # Choice 1: Include the candidate at the current index (allowing reuse)
        Sum = total + nums[index]
        subset.append(nums[index])
        self.solve(index, Sum, subset, nums, target, result)  # Same index for reuse

        # Backtrack: Remove the candidate just added
        Sum = total  # Reset Sum to the value before including the candidate
        subset.pop()

        # Choice 2: Skip the candidate and move to the next index
        self.solve(index + 1, Sum, subset, nums, target, result)

    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        result = []
        self.solve(0, 0, [], candidates, target, result)
        return result

Code Explanation

The solve function explores all possible combinations using backtracking. The key insight is in the recursive calls: when we include a candidate, we call self.solve(index, Sum, ...) with the same index, allowing us to use the same number again. When we skip a candidate, we call self.solve(index + 1, Sum, ...) to move to the next number. The backtracking step (subset.pop()) ensures we clean up after trying each choice, so other branches start with a fresh state. We use subset.copy() when adding to results to prevent future modifications from affecting already stored combinations.

Dry Run

Let’s trace through: candidates = , target = 7

Start: index=0, total=0, subset=[]

Try including 2 (index=0):

• subset=, total=2, index=0 (stay at same position)Try including 2 again:
  • subset=, total=4, index=0Try including 2 again:
    • subset=, total=6, index=0Try including 2 again:
      • total=8 > 7, prune this path
      Skip 2, try 3:
      • subset=, total=6, index=1
        • subset=, total=9 > 7, prune
        • Skip 3: index=2 >= len(nums), return
    Skip 2, try 3:
    • subset=, total=4, index=1
      • subset=, total=7 = target → add to result
      • Skip 3: index=2 >= len(nums), return
  Skip 2, try 3:
  • subset=, total=2, index=1
    • subset=, total=5, index=1
      • subset=, total=8 > 7, prune
      • Skip 3: index=2 >= len(nums), return
    • Skip 3: index=2 >= len(nums), return

Skip 2, try 3 (index=1):

• subset=[], total=0, index=1
  • subset=, total=3, index=1
    • subset=, total=6, index=1
      • subset=, total=9 > 7, prune
      • Skip 3: index=2 >= len(nums), return
    • Skip 3: index=2 >= len(nums), return
  • Skip 3: index=2 >= len(nums), return

Result: []

Time and Space Complexity

• Time Complexity: O(N^(T/M)) – Where N is the number of candidates, T is the target, and M is the minimal value among candidates. In worst case, we might have T/M levels in recursion tree.
• Space Complexity: O(T/M) – The recursion stack depth can go up to T/M levels (when we keep choosing the smallest candidate).

Simplifying It

This backtracking approach is like trying to make exact change using unlimited coins. At each step, you decide: “Should I take this coin again, or should I move to the next type of coin?” The beauty is that you can keep taking the same coin until you either hit your target or go over it. The backtracking ensures you try all possible combinations systematically, you explore one path completely, then backtrack and try another path. The key difference from other subset problems is that here we can reuse elements, which is why we don’t increment the index when including a candidate.

This problem is perfect for understanding how backtracking can handle problems with repetition allowed, and it’s a common interview question that tests your ability to handle recursive choices with state management!

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.