Leetcode - 39. Combination Sum

The Combination Sum problem is a classic backtracking question from LeetCode (#39).

We are given:

• An array of positive integers candidates (no duplicates inside).
• A target integer target.

We must return all unique combinations where the chosen numbers add up exactly to target.
Numbers can be reused unlimited times.

---

🎯 Example

candidates = [2, 3, 6, 7], target = 7

Output:

[
  [2, 2, 3],
  [7]
]

Why?

• [2, 2, 3] → adds to 7
• [7] → also adds to 7
• No other valid combinations exist.

---

🧠 Approach – Backtracking (DFS)

This is a search problem. Think of it like exploring all possible "paths" of numbers until:

• The sum equals target → ✅ valid combination
• The sum exceeds target → ❌ invalid, stop
• We’ve tried all numbers → ❌ stop

We use DFS + backtracking:

1. Start at index 0 with an empty path [] and total 0.
2. At each step:

• Either include the current candidate (stay on same index since we can reuse it).
• Or skip it and move to the next index.
  1. Whenever total === target, we push a copy of the path into results.
  2. Backtrack by popping out the last choice and continue exploring.

---

✅ Code (JavaScript)

/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
var combinationSum = function (candidates, target) {
    let res = [];

    const dfs = (i, curr, total) => {
        if (total === target) {
            res.push([...curr]); // store valid combination
            return;
        }

        if (i >= candidates.length || total > target) {
            return; // stop exploring
        }

        // 1. Choose the current number
        curr.push(candidates[i]);
        dfs(i, curr, total + candidates[i]); // stay on i since reuse is allowed
        curr.pop(); // backtrack

        // 2. Skip the current number
        dfs(i + 1, curr, total);
    };

    dfs(0, [], 0);
    return res;
};

---

⏱️ Time and Space Complexity

Let’s analyze:

Time Complexity

• In the worst case, each number can be chosen multiple times until we exceed the target.
• The height of the recursion tree is at most target / min(candidates).
• At each level, we branch into choose or skip → about 2^n style growth.
• Worst-case complexity: O(2^n * t) where t is the target (because we keep adding numbers until reaching it).

In practice, it runs much faster due to pruning (total > target).

Space Complexity

• O(target/min(candidates)) for the recursion depth (stack space).
• Plus storage for results, which could be exponential in the number of combinations.

---

🚀 Key Takeaways

• Backtracking is perfect when we need all possible solutions.

• The trick is in branching:

  • Reuse the current candidate → dfs(i, ...)
  • Skip it → dfs(i+1, ...)

• The stopping condition if (i >= candidates.length || total > target) prevents infinite recursion.

---