Combination Sum

Pick numbers from a list, reusing any of them as often as needed, so they add up to a target.

The idea

This is subsets with two twists: a running sum that must hit an exact target, and reuse. Passing i (not i + 1) back into the recursive call lets the same candidate be chosen again, while start still stops a combination from being built in a different order.

Code

public static void Combine(int[] cand, int target, int start, List<int> path, int sum, List<List<int>> result) {
    if (sum == target) { result.Add(new List<int>(path)); return; }
    if (sum > target) return;
    for (int i = start; i < cand.Length; i++) {
        path.Add(cand[i]);
        Combine(cand, target, i, path, sum + cand[i], result);
        path.RemoveAt(path.Count - 1);
    }
}

Tips

• Check sum > target before looping, not inside it. That one line prunes an entire exponential branch in one step.
• Sort the candidates first in real code; it makes the overshoot check fire earlier.

In the .NET library

The sum is tracked as an int parameter instead of recomputed from path each time, so the prune check is O(1) instead of O(n). Recomputing from the list would still be correct, just slower.