Combination Sum: reusable candidates, keep index to dedup

• Combination Sum – find all unique combinations from a set of distinct candidates that sum to a target, where each candidate can be reused unlimited times.
• Backtracking – build combinations by choosing candidates from a start index onward, subtracting from the remaining target, and undoing each choice after recursion.
• Reuse – passing the same index on recursion allows picking the same candidate again; passing index + 1 would disallow reuse.
• Deduplication – the start index prevents looking backward, ensuring non-decreasing order and eliminating order-based duplicates.
• Pruning – sorting candidates and breaking when a candidate exceeds the remaining target cuts the search sharply.

What is the Combination Sum problem?

Given an array of distinct positive integers (candidates) and a target integer, find all unique combinations of candidates that sum to the target. Each candidate may be used an unlimited number of times. The same combination in different order counts as one (so [2,3] and [3,2] are the same).

This is LeetCode 39.

package com.bank.service;

// Candidates (deposit denominations): [2, 3, 6, 7]
// Target: 7
// Valid combinations: [2,2,3] and [7]

How does the backtracking solution work?

• Carry a start index, the remaining target, and a current path. At each level:
• If remaining is zero, record a copy of the path (valid combination found).
• If remaining is negative, return (prune this branch).
• Loop from the start index over candidates. For each candidate, add it to the path, recurse with the same index 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 CombinationSum {

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

    private void backtrack(int[] candidates, int remaining,
                           int start, List<Integer> path,
                           List<List<Integer>> result) {
        if (remaining == 0) {
            result.add(new ArrayList<>(path)); // record a copy
            return;
        }
        for (int i = start; i < candidates.length; i++) {
            if (candidates[i] > remaining) {
                break; // prune: all further candidates are too large
            }
            path.add(candidates[i]);
            backtrack(candidates, remaining - candidates[i], i, path, result);
            path.remove(path.size() - 1); // backtrack
        }
    }

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

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

Why recurse with the same index?

Passing i (not i + 1) on recursion allows the same candidate to be chosen again. This is what enables unlimited reuse. If you passed i + 1, each candidate could only be used once, which is the Combination Sum II variant.

// Allows reuse: recurse with same index i
backtrack(candidates, remaining - candidates[i], i, path, result);

// Disallows reuse: recurse with i + 1
backtrack(candidates, remaining - candidates[i], i + 1, path, result);

How does the start index prevent duplicates?

The loop starts at start, never going back to earlier candidates. This fixes a non-decreasing order, so each distinct multiset is produced exactly once. Without this, both [2,3] and [3,2] would be generated.

package com.bank.service;

public class DedupExplanation {
    // With start index:
    //   Start at 0: can pick 2,3,6,7
    //   After picking 2, still start at 0: can pick 2,3,6,7
    //   After picking 3, start at 1: can pick 3,6,7 (not 2)
    //   This prevents [3,2] since 2 comes before 3
}

What about the banking domain use case?

At the National Bank of India, the cash dispensing module needs to enumerate every way to make up an exact withdrawal amount using available note denominations. Each denomination can be dispensed in unlimited quantity.

package com.bank.service;

import java.util.List;

public class CashDispenser {
    public static void main(String[] args) {
        int[] denominations = {100, 200, 500};
        int withdrawalAmount = 700;

        CombinationSum solver = new CombinationSum();
        List<List<Integer>> plans = solver.combinationSum(denominations, withdrawalAmount);

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

Ways to dispense 700:
  Notes: [100, 100, 100, 100, 100, 100, 100]
  Notes: [100, 100, 100, 100, 100, 200]
  Notes: [100, 100, 100, 200, 200]
  Notes: [100, 100, 500]
  Notes: [100, 200, 200, 200]
  Notes: [200, 500]

What are the edge cases?

• Target equals zero: return one combination (the empty set).
• No candidates can reach the target: return an empty list.
• Single candidate: only works if the target is divisible by it.
• Very large target with small candidates: the recursion tree is deep; the early-break prune helps.

package com.bank.service;

public class CombSumEdgeCases {
    public static void main(String[] args) {
        CombinationSum solver = new CombinationSum();
        System.out.println("Single: " + solver.combinationSum(new int[]{3}, 9));
        System.out.println("Impossible: " + solver.combinationSum(new int[]{5}, 3));
    }
}

Single: [[3, 3, 3]]
Impossible: []

How is this different from Combination Sum II?

In Combination Sum II (LeetCode 40), each candidate can be used at most once, and the input may contain duplicates. The fix: recurse with i + 1 and skip consecutive equal candidates when the previous was not used.

| Feature | Combination Sum (LC 39) | Combination Sum II (LC 40) |
|---|---|---|
| Candidate reuse | Unlimited | At most once |
| Input duplicates | No | Possible |
| Recurse index | Same index i | Next index i + 1 |
| Dedup for duplicates | Not needed | Skip equal consecutive |

What are common interview follow-up questions?

• What if each candidate can only be used once? (Recurse with i + 1.)
• What is the time complexity? (Exponential, bounded by the number of valid combinations times their average length.)
• How does sorting help? (Enables early-break pruning when a candidate exceeds the remaining target.)
• How do you avoid generating [2,3] and [3,2]? (Start index prevents going backward.)
• What if the input has duplicates? (Sort and skip consecutive equal values: Combination Sum II.)