Recursion & BacktrackingMediumO(n^(target/min)) time · O(target/min) space

Combination Sum

Mahabharata — The War Council's Budget — All Ways to Spend Exactly target Using Unlimited Supplies

लक्ष्य राशि — असीमित उपयोग से। चुनो फिर वही — या अगला — जब लक्ष्य शून्य हो तब सफलता॥

*Target sum — with unlimited reuse. Pick again or the next — when target reaches zero: success.*

The Story

Find all combinations of candidates (unlimited reuse allowed) that sum to target. Return all unique combinations.

For `candidates=[2,3,6,7]`, target=7: [[2,2,3],[7]].

**Backtracking:** - Start from index `start` (avoids re-using previous elements to prevent duplicates) - At each step: pick candidates[i] (can pick same element again since i stays same in recursive call) - Subtract from remaining target, recurse - Backtrack: remove last added element

```java void backtrack(List<List<Integer>> res, List<Integer> path, int[] cand, int target, int start) { if (target == 0) { res.add(new ArrayList<>(path)); return; } // Found! if (target < 0) return; // Overshot for (int i=start; i<cand.length; i++) { path.add(cand[i]); // Choose backtrack(res, path, cand, target-cand[i], i); // Explore (same i = reuse allowed) path.remove(path.size()-1); // Unchoose } } ```

Trace `[2,3,6,7]`, target=7: - path=[]: try 2 (target→5), 3 (target→4), 6 (target→1), 7 (target→0✓) - [2]: try 2(→3), 3(→2), 6(→−1✗), 7(→−2✗) - [2,2]: try 2(→1), 3(→0✓→add[2,2,3]), ... - [2,2,2]: try 2(→−1✗), ... - [2,3]: try 2(→0✓→add... wait target=7-2-3=2), try 2(0✓→[2,2,3])...

Eventually finds [[2,2,3],[7]] ✓

**Key difference from permutations:** We pass `start=i` (not `start=i+1`) to allow reusing the same element.

The DFS without Index Constraint

Start from index 0 each time (creates duplicates). Filter unique solutions. Much slower.

java

// Correct solution IS the optimal one. No simpler approach.
// The 'start' index is what prevents duplicates.

The Start-Index Reuse Backtracking

Backtrack with start index. Choose candidates[i], recurse with same i (reuse OK). Unchoose. Target==0: add to result. Target<0: prune.

java

public List<List<Integer>> combinationSum(int[] candidates, int target) {
    List<List<Integer>> res = new ArrayList<>();
    backtrack(res, new ArrayList<>(), candidates, target, 0);
    return res;
}

void backtrack(List<List<Integer>> res, List<Integer> path,
               int[] cand, int target, int start) {
    if (target == 0) { res.add(new ArrayList<>(path)); return; }
    for (int i = start; i < cand.length; i++) {
        if (cand[i] > target) continue;  // Pruning (if sorted)
        path.add(cand[i]);
        backtrack(res, path, cand, target - cand[i], i);  // i not i+1
        path.remove(path.size() - 1);
    }
}

Step-by-Step Walkthrough

candidates=[1], target=3
[1,1,1]: target goes 3→2→1→0 → add [1,1,1]
Result: [[1,1,1]] ✅

Deep Insight

**i vs i+1 in recursive call:** - `backtrack(..., i)`: allows reusing candidates[i] → Combination Sum (unlimited reuse) - `backtrack(..., i+1)`: each element used at most once → Combination Sum II / subsets

**Sorting enables early pruning:** `if (cand[i] > target) break` (if sorted). Instead of `continue` for just cand[i], we can `break` since all subsequent candidates are also > target.

**Uniqueness:** Using `start` index prevents [3,2] after finding [2,3] — we only consider candidates at index >= start, ensuring non-decreasing order in each combination.

Complexity Analysis

Approach	Time	Space	Note
Brute Force	O(n^(target/min))	O(target/min)	Worst case: using smallest candidate repeatedly
Optimal	O(n^(target/min))	O(target/min)	Same as brute force — necessary to generate all combinations

Pattern Recognition

✅ Combination sum with reuse → i stays same in recursive call
✅ Without reuse → i+1 in recursive call
✅ Start index prevents duplicate combinations
✅ target==0 → success; target<0 → prune

**LeetCode Trigger Phrases:**
→ "combination sum" (unlimited reuse)
→ "combination sum II" (no reuse, may have duplicates)
→ All combinations summing to target

Bhagavad Gita 3.12

इष्टान्भोगान्हि वो देवा दास्यन्ते यज्ञभाविताः। तैर्दत्तानप्रदायैभ्यो यो भुङ्क्ते स्तेन एव सः॥

The gods, nourished by yajna, will give you desired enjoyments. But one who enjoys their gifts without offering to them is indeed a thief.

Connection: The combination sum seeks all ways to reach the target — each combination representing a valid arrangement of contributions. Like the yajna where different offerings combine to achieve a sacred goal, the algorithm finds every combination of candidates (each used as many times as needed) that sums exactly to the target. The start index ensures no combination is double-counted — each sacred arrangement is unique.