Combination sum II

Pick numbers that add up to a target, each number at most once, where the list may hold duplicates. Sort, skip repeated values at one depth, and stop as soon as a number is too big.

The idea

This is Subsets II with a running total. Recursing with i + 1 uses each position at most once. Sorting puts equal values side by side, so skipping c[i] == c[i - 1] at the same depth stops [1, 2a, 2b] and [1, 2b, 2c] from both appearing. Sorting also enables the prune: once c[i] is bigger than what remains, every value after it is too, so break out of the loop instead of trying them.

Code

public IList<IList<int>> CombinationSum2(int[] candidates, int target) {
    Array.Sort(candidates); // duplicates side by side, and small values first
    var result = new List<IList<int>>();
    Backtrack(candidates, target, 0, new List<int>(), result);
    return result;
}

void Backtrack(int[] c, int remain, int start, List<int> path, List<IList<int>> result) {
    if (remain == 0) { result.Add(new List<int>(path)); return; }
    for (int i = start; i < c.Length; i++) {
        if (i > start && c[i] == c[i - 1]) continue; // same value already tried at this depth
        if (c[i] > remain) break; // sorted: every later value is too big as well
        path.Add(c[i]);
        Backtrack(c, remain - c[i], i + 1, path, result); // i + 1: each number used once
        path.RemoveAt(path.Count - 1);
    }
}

Tips

• Break, not continue, on c[i] > remain: the array is sorted, so nothing later can fit either.
• Compare with Combination Sum (reuse allowed), which recurses with i instead of i + 1 and needs no duplicate check.
• The LeetCode example 10, 1, 2, 7, 6, 1, 5 with target 8 gives [1, 1, 6], [1, 2, 5], [1, 7], [2, 6]; its recursion tree is too wide to draw here, so the default is the smaller second example.

In the .NET library

Array.Sort sorts the caller's array in place. If the caller must keep its order, sort a copy made with (int[])candidates.Clone() or candidates.ToArray() (LINQ).