Start learning free

LESSON 355 OF 539 · BACKTRACKING

Combination Sum in C#: Backtracking with Sorted Candidates

Practice O(nt/m) Read the full explanation

Given an array of distinct integers candidates and an integer target, return every combination of numbers from candidates that adds up to target.

The same number may be chosen any number of times. Two combinations are the same when they use the same numbers the same number of times, whatever the order: [2, 2, 3] and [3, 2, 2] are one combination, and it must appear only once.

Write the numbers of each combination in ascending order, and return the combinations in lexicographic order: compare two combinations number by number, and the first position where they differ decides which one comes first. If no combination adds up to target, return an empty array.

 

Example 1:

Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]
Explanation: 2 + 2 + 3 = 7, using the 2 twice, and 7 alone is 7.
No other combination adds up to 7. [2,2,3] comes first because its first number, 2, is smaller than 7.

Example 2:

Input: candidates = [5,2,3], target = 8
Output: [[2,2,2,2],[2,3,3],[3,5]]
Explanation: The candidates are not sorted, but every combination is written in ascending order.
[2,2,2,2] and [2,3,3] both start with 2; at their second number, 2 is smaller than 3. [3,5] starts with 3, so it comes last.

Example 3:

Input: candidates = [2], target = 1
Output: []
Explanation: The only candidate, 2, is already bigger than 1, so no combination adds up to 1.

 

Constraints:

  • 1 <= candidates.length <= 30
  • 2 <= candidates[i] <= 40
  • All the numbers in candidates are distinct.
  • 1 <= target <= 40

Note:

The tutorial uses backtracking. Sort candidates, then build a combination one number at a time: try every candidate from the position of the last number chosen onward (that same number included, since numbers can repeat), go deeper with what is left of target, then remove the number again and try the next one. Starting from the last chosen position builds each combination exactly once, already in ascending order, and the combinations come out in lexicographic order. Because the candidates are sorted, the loop can stop at the first one that is bigger than what is left.

The search is exponential: with n candidates, a target t and a smallest candidate m, a combination has at most t / m numbers, and each of them is one of n candidates, so the time is O(nt/m) in the worst case. Besides the answer, the extra space is O(t / m): the combination being built and one call per number in it.

STEP 1 OF 12
    Ctrl + Enter to check

    C# · BACKTRACKING

    Combination Sum in C#, explained

    Problem overview

    The method CombinationSum receives candidates, an int[] of distinct numbers, and an int target. It returns every combination of candidates that adds up to target, as a List<List<int>>. A number can be used any number of times. Two combinations are the same when they use the same numbers the same number of times, so [2, 2, 3] and [3, 2, 2] count as one and must appear once.

    Each combination is written in ascending order, and the combinations are returned in lexicographic order: compare number by number, and the first difference decides. If nothing adds up to target, the result is an empty list.

    For candidates = [2, 3, 6, 7] and target = 7, the answer is [[2, 2, 3], [7]]: 2 + 2 + 3 = 7 and 7 alone is 7. For candidates = [5, 2, 3] and target = 8, the answer is [[2, 2, 2, 2], [2, 3, 3], [3, 5]], even though the input isn't sorted. For candidates = [2] and target = 1, the answer is [].

    Approach: build a combination one number at a time

    This is a search over choices. A partial combination has a total, and the amount remaining is target minus that total. At each step the search picks the next number to add, goes deeper with a smaller remaining amount, then removes the number again and tries the next one. Taking a choice back so another can be tried is the "back" in backtracking. When remaining reaches exactly 0, the combination is complete and gets saved.

    Two ideas keep the output correct without any duplicate removal:

    • Sort the candidates, and only move forward. A call may only choose candidates from index i onward, and the next call starts at the index just chosen, not at 0. Starting at the same index allows a number to repeat. Never going back means a combination is built only in ascending order, so [2, 2, 3] can be found but [3, 2, 2] can't, and no combination is built twice.
    • The order comes out lexicographic. With the candidates sorted and the loop trying them in order, smaller first numbers are explored before larger ones, so the combinations are found in exactly the order the answer needs.

    Sorting also allows a cut-off. Once a candidate is larger than what remains, every later candidate is larger still, so the loop can stop with break instead of testing them.

    Step by step

    CombinationSum: set up and start

    1. Sort candidates with Array.Sort, which sorts the array in place in ascending order.
    2. Create result, an empty List<List<int>>. Each combination is itself a list.
    3. Start the search with Backtrack(candidates, target, 0, new List<int>(), result). Nothing is chosen yet, all of target remains, and every candidate from index 0 may be used.
    4. Return result, which the helper has filled.

    Backtrack: add one number and recurse

    1. Declare Backtrack as a public void method with candidates, remaining, i (the first index it may use), current (the combination so far) and result.
    2. Test remaining == 0. Then the numbers in current add up to exactly the target.
    3. Save a copy with result.Add(new List<int>(current)), then return. A copy is needed because current keeps changing as the search goes on. Every candidate is at least 2, so adding more numbers would overshoot anyway.
    4. Loop with j from i while j < candidates.Length. These are the numbers the combination may take next.
    5. Stop at a number that is too big: if candidates[j] > remaining, break.
    6. Choose candidates[j] by adding it to the end of current.
    7. Recurse with remaining - candidates[j] and j as the first index. Passing j rather than j + 1 lets the same number be taken again.
    8. Undo the choice with current.RemoveAt(current.Count - 1), so current is what it was before this turn of the loop.

    The solution in C#

    class Solution {
    public List<List<int>> CombinationSum(int[] candidates, int target) {
        Array.Sort(candidates);
        List<List<int>> result = new List<List<int>>();
        Backtrack(candidates, target, 0, new List<int>(), result);
        return result;
    }

    public void Backtrack(int[] candidates, int remaining, int i, List<int> current, List<List<int>> result) {
        if (remaining == 0) {
            result.Add(new List<int>(current));
            return;
        }
        for (int j = i; j < candidates.Length; j++) {
            if (candidates[j] > remaining) {
                break;
            }
            current.Add(candidates[j]);
            Backtrack(candidates, remaining - candidates[j], j, current, result);
            current.RemoveAt(current.Count - 1);
        }
    }
}

    The C# details worth knowing:

    • Lists are references. If the code wrote result.Add(current), every entry of result would be the same list object, and at the end all of them would be empty, because the undo steps empty current. new List<int>(current) is the copy constructor: it builds a separate list with the same numbers.
    • Array.Sort changes the caller's array. It sorts candidates in place and returns nothing. After the call, the caller's array is sorted too.
    • RemoveAt takes an index. current.RemoveAt(current.Count - 1) removes the last element. current.Remove(x) would remove the first element equal to x, which could be a different one when numbers repeat.
    • Nested generics. List<List<int>> is a list whose elements are lists of int. Each inner list can have a different length.
    • The helper is shared state. One current list and one result list are passed through all the calls. That is why the undo step matters: all the calls share current.

    Complexity

    Let n be the number of candidates, t the target and m the smallest candidate.

    Time: exponential, about O(n^(t/m)) in the worst case. A combination has at most t / m numbers, because each is at least m, and each position is one of n candidates. The break and the forward-only index prune much of that, but the bound for the worst case stays exponential. Copying each finished combination also costs time proportional to its length.

    Space: O(t / m) besides the answer. The combination being built and the call stack are both at most t / m long.

    Edge cases and common mistakes

    • No combination. With candidates = [2] and target = 1, the only candidate is already too big, the loop breaks at once, and the result is [].
    • Unsorted input. Without the sort, the break would skip valid candidates that come after a big one, and the combinations wouldn't be in ascending order.
    • Starting the loop at 0 in every call. This builds [2, 2, 3], [2, 3, 2] and [3, 2, 2] as separate answers.
    • Passing j + 1. This forbids using a number twice, which solves a different problem. For [2, 3, 6, 7] and target 7, it would lose [2, 2, 3].
    • Forgetting the undo. current grows with every choice, and later combinations contain leftovers from earlier ones.
    • Using continue instead of break. It gives the same answer, but the loop keeps testing numbers that can't fit.

    Testing

    • candidates = [2, 3, 6, 7], target = 7 gives [[2,2,3],[7]].
    • candidates = [5, 2, 3], target = 8 gives [[2,2,2,2],[2,3,3],[3,5]].
    • candidates = [2, 3, 5], target = 8 gives [[2,2,2,2],[2,3,3],[3,5]].
    • candidates = [2], target = 1 gives [].
    Keep going with C#500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free