Combination Sum (Backtracking with Reuse)

• Combination Sum – find every multiset of candidates, drawn with unlimited repeats, whose total equals a target.
• Reuse rule – recurse with the same index i (not i + 1) so a candidate can appear any number of times.
• Deduplication – loop starts at start, never going backward, which fixes non-decreasing order and prevents order-based duplicates.
• Two base cases – remaining equals zero means record a valid combination; remaining goes negative means prune.
• Pruning – sort candidates; if candidates[i] > remaining, break because all later candidates are larger.

What is the Combination Sum problem?

Given a set of distinct positive numbers (candidates) and a target, find all unique combinations where the candidates sum to the target. Each candidate may be used an unlimited number of times. The same combination in a different order counts as one combination.

This is LeetCode 39 and one of the most commonly asked backtracking problems.

package com.bank.service;

// Candidates: [2, 3, 6, 7], Target: 7
// Combinations: [2,2,3] and [7]

How does the backtracking work?

• The state is the remaining target and the start index. The two base cases drive everything:
• Remaining equals zero: record a copy of the current path.
• Remaining is negative: return immediately (prune).

The loop runs from the start index over candidates. For each candidate, add it to the path, recurse with the same index (allowing reuse) and reduced remaining, then remove it (backtrack).

package com.bank.service;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class CombinationSumReuse {

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

    private void backtrack(int[] cand, int remaining, int start,
                           List<Integer> path, List<List<Integer>> result) {
        if (remaining == 0) {
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i = start; i < cand.length; i++) {
            if (cand[i] > remaining) break; // prune
            path.add(cand[i]);
            backtrack(cand, remaining - cand[i], i, path, result); // same index
            path.remove(path.size() - 1);
        }
    }

    public static void main(String[] args) {
        CombinationSumReuse solver = new CombinationSumReuse();
        System.out.println(solver.combinationSum(new int[]{2, 3, 6, 7}, 7));
    }
}

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

Why pass the same index for reuse?

Passing i (not i + 1) on recursion means the same candidate can be chosen again at the next level. If you passed i + 1, each candidate would be used at most once, which is the Combination Sum II variant.

// Reuse allowed: same index
backtrack(cand, remaining - cand[i], i, path, result);

// No reuse: next index
backtrack(cand, remaining - cand[i], i + 1, path, result);

How does the start index prevent duplicates?

The loop starts at start and never goes backward. This forces combinations to be in non-decreasing order, so each distinct multiset appears exactly once. Without this, [2,3] and [3,2] would both be generated.

package com.bank.service;

public class DedupDemo {
    // With start=0 initially:
    //   Picking 2 then 3 is allowed (index 0, then 1)
    //   Picking 3 then 2 is impossible (index 1, cannot go back to 0)
    // So [2,3] appears once, [3,2] never appears
}

How does sorting enable pruning?

Sorting the candidates ensures that once a candidate exceeds the remaining target, all subsequent candidates are even larger. You can break out of the loop entirely, pruning the entire right side of the search tree.

for (int i = start; i < cand.length; i++) {
    if (cand[i] > remaining) break; // everything after is larger too
    // ...
}

What about the banking domain use case?

At the National Bank of India, the cash dispensing module enumerates every way to assemble an exact withdrawal amount from available note denominations. Each denomination can be dispensed in unlimited quantity.

package com.bank.service;

import java.util.List;

public class CashDispenserReuse {
    public static void main(String[] args) {
        int[] notes = {100, 200, 500};
        int amount = 600;

        CombinationSumReuse solver = new CombinationSumReuse();
        List<List<Integer>> plans = solver.combinationSum(notes, amount);

        System.out.println("Ways to dispense " + amount + ":");
        for (List<Integer> plan : plans) {
            System.out.println("  " + plan);
        }
    }
}

Ways to dispense 600:
  [100, 100, 100, 100, 100, 100]
  [100, 100, 100, 100, 200]
  [100, 100, 200, 200]
  [100, 500]
  [200, 200, 200]

How is this different from Combination Sum II and III?

| Variant | Reuse | Input duplicates | Index rule | LeetCode |
|---|---|---|---|---|
| Combination Sum | Unlimited | No | Same index i | 39 |
| Combination Sum II | At most once | Yes | i + 1, skip equal | 40 |
| Combination Sum III | At most once | No (1-9 only) | i + 1 | 216 |

All share the same backtracking skeleton with small tweaks to the index and dedup rules.

What are the edge cases?

• Target equals a single candidate: one combination of length 1.
• No valid combination exists: return an empty list.
• Single candidate: works only if target is divisible by it.
• Very large target with small candidates: deep recursion tree; pruning is essential.

package com.bank.service;

public class CombSumReuseEdgeCases {
    public static void main(String[] args) {
        CombinationSumReuse solver = new CombinationSumReuse();
        System.out.println(solver.combinationSum(new int[]{7}, 7));   // [[7]]
        System.out.println(solver.combinationSum(new int[]{5}, 3));   // []
        System.out.println(solver.combinationSum(new int[]{3}, 9));   // [[3,3,3]]
    }
}

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

What are common interview follow-up questions?

• What if each candidate can be used at most once? (Pass i + 1.)
• What if the input has duplicates? (Sort and skip consecutive equal values: Combination Sum II.)
• What is the time complexity? (Exponential, bounded by the number of valid combinations.)
• How does sorting help? (Enables early-break pruning.)
• Can you use DP instead? (For counting, yes. For listing all combinations, backtracking is cleaner.)