Combination Sum Backtracking Java | Fresher Interview

Direct Answer

Use backtracking: at each step try each candidate from a start index, subtract it from the remaining target, and recurse. If the remaining target hits 0, record the combination; if it goes negative, prune that branch. To allow reusing a number, recurse with the same index; to use each once, recurse with i + 1. Sorting enables an early break when candidate > remaining.

Deep Dive & Architecture

Each recursive call represents two pieces of state: the amount still needed and the first candidate index that may be chosen. The start index keeps combinations in one order, so [2, 2, 3] is produced without also producing [3, 2, 2].

Worked example: candidates [2, 3, 6, 7], target 7

Choose 2; the remainder becomes 5. Choose 2 again; the remainder becomes 3. Choosing 2 once more leaves 1, and because the sorted candidates are now all too large, that branch stops. Backtrack one choice, try 3, and the remainder reaches 0, so copy [2, 2, 3] into the result. Back at the root, choosing 7 also reaches 0 and records [7].

Passing the same index into the next call allows a candidate to be reused. Passing i + 1 would describe the different rule where each input item can be used once. After every recursive call, remove the last item from the path so the next branch starts from the correct state.

Sorting is not required for correctness, but it enables an early break as soon as a candidate is greater than the remaining amount. The running time is output-sensitive because the search may explore many valid partial combinations.

Code Example

List<List<Integer>> combinationSum(int[] cand, int target) {
    Arrays.sort(cand);                       // enables early break
    List<List<Integer>> res = new ArrayList<>();
    backtrack(cand, target, 0, new ArrayList<>(), res);
    return res;
}
void backtrack(int[] c, int rem, int start, List<Integer> path, List<List<Integer>> res) {
    if (rem == 0) { res.add(new ArrayList<>(path)); return; }   // hit target
    for (int i = start; i < c.length; i++) {
        if (c[i] > rem) break;               // PRUNE: sorted, rest are larger
        path.add(c[i]);                      // choose
        backtrack(c, rem - c[i], i, path, res);  // i = allow reuse
        path.remove(path.size() - 1);        // un-choose
    }
}

// cand={2,3,6,7}, target=7 -> [2,2,3] and [7]

Common Mistakes & Pitfalls

• No start index: iterating from 0 each time produces duplicate combinations like [2,3] and [3,2].
• Missing prune: not returning when remaining < 0 wastes huge amounts of work.
• Wrong reuse: recurse with i to reuse, i + 1 for single-use - pick deliberately.
• Adding the reference: store a copy of path on success.