Combination Sum II: each number used once, skip duplicates

• Combination Sum II – find all unique combinations from a candidate array (with possible duplicates) that sum to a target, using each candidate at most once.
• Sort first – enables duplicate skipping and early pruning.
• Use-once – recurse with i + 1 instead of i, ensuring each element is consumed only once.
• Duplicate skip – if (i > start && cand[i] == cand[i-1]) continue prevents duplicate combinations.
• Prune – break when cand[i] > remaining because the array is sorted.

What is the Combination Sum II problem?

Given an array of candidates (which may contain duplicates) and a target, find all unique combinations where each candidate is used at most once and the combination sums to the target. For example, with candidates [10, 1, 2, 7, 6, 1, 5] and target 8, the valid combinations are [1,1,6], [1,2,5], [1,7], and [2,6].

package com.bank.dsa;

import java.util.List;

public interface CombinationSumSolver {
    List<List<Integer>> combinationSum2(int[] candidates, int target);
}

How does the sort-plus-backtrack approach work?

Sort the candidates so duplicates are adjacent. In the backtracking loop, for each candidate at index i, subtract it from the remaining target and recurse with i + 1 (use-once). Skip same-level duplicates with the i > start guard. Record the path when the remaining target reaches zero. Prune by breaking when the candidate exceeds the remaining target.

package com.bank.dsa;

import java.util.*;

public class CouponRedemptionService {
    public static List<List<Integer>> findCombinations(int[] coupons, int target) {
        Arrays.sort(coupons);
        List<List<Integer>> result = new ArrayList<>();
        backtrack(coupons, target, 0, new ArrayList<>(), result);
        return result;
    }

    private static void backtrack(int[] cand, int remain, int start,
                                   List<Integer> path, List<List<Integer>> result) {
        if (remain == 0) {
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i = start; i < cand.length; i++) {
            if (cand[i] > remain) break; // prune: sorted, so all remaining too large
            if (i > start && cand[i] == cand[i - 1]) continue; // skip duplicate

            path.add(cand[i]);
            backtrack(cand, remain - cand[i], i + 1, path, result); // i+1: use once
            path.remove(path.size() - 1);
        }
    }

    public static void main(String[] args) {
        int[] coupons = {500, 100, 200, 300, 100, 400};
        int target = 600;
        List<List<Integer>> combos = findCombinations(coupons, target);
        for (List<Integer> combo : combos) {
            System.out.println(combo);
        }
    }
}

[100, 100, 400]
[100, 200, 300]
[100, 500]
[200, 400]

Why recurse with i+1 instead of i?

Recursing with i + 1 ensures each candidate is used at most once. In Combination Sum (the first version), you recurse with i to allow unlimited reuse of the same candidate. The i + 1 rule is what enforces the "use at most once" constraint.

// Combination Sum: unlimited reuse
backtrack(cand, remain - cand[i], i, path, result);

// Combination Sum II: use at most once
backtrack(cand, remain - cand[i], i + 1, path, result);

Why is the duplicate skip needed?

Even with the use-once rule, duplicate candidates at the same level can produce duplicate combinations. For example, with [1, 1, 6] and target 8, choosing the first 1 at level 0 and choosing the second 1 at level 0 both lead to [1, ...] paths that can produce the same combination. The skip guard prevents the second identical choice at the same level.

// Without skip: [1a, 1b, 6] and [1b, 1a, 6] are generated as [1,1,6] twice
// With skip: only [1a, ...] path is explored at level 0
if (i > start && cand[i] == cand[i - 1]) continue;

How does the pruning work?

Because the candidates are sorted, once cand[i] > remain, all subsequent candidates are also too large. Breaking out of the loop prunes these branches entirely. This can save significant work on arrays with many large candidates.

if (cand[i] > remain) break;
// cand[i] <= cand[i+1] <= ... (sorted)
// So none of them can be part of a valid combination

How is this different from Combination Sum and Subsets II?

All three problems use the same sort-plus-backtrack skeleton with the same-level-duplicate skip guard. The differences are in what you record and whether you reuse elements.

| Problem | Recurse With | Record When | Skip Guard |
|---|---|---|---|
| Combination Sum | i (reuse) | remain == 0 | No duplicates in input |
| Combination Sum II | i+1 (use once) | remain == 0 | i > start && cand[i] == cand[i-1] |
| Subsets II | i+1 | Every entry | i > start && nums[i] == nums[i-1] |

What are common mistakes?

The most common mistake is recursing with i instead of i + 1, which allows reuse and produces wrong results for the "use once" constraint. Another is using break instead of continue in the skip guard, which stops the entire loop instead of just skipping one element.

// Wrong: break stops the whole loop
if (i > start && cand[i] == cand[i-1]) break;
// Correct: continue skips only this element
if (i > start && cand[i] == cand[i-1]) continue;

What should a senior engineer know?

A senior engineer recognises the combination-from-multiset pattern as a single template shared with Subsets II and Combination Sum. They can switch between the three variants by adjusting the recursion index and the recording condition. They mention the pruning optimisation and explain why the use-once rule plus the duplicate skip together are necessary and sufficient.