Combination Sum in c#

Programming C#
1

The “Combination Sum” problem involves finding all unique combinations of numbers from a given list that add up to a specific target sum. Each number in the list can be used unlimited times in the combinations.

Problem Statement

Given a list of distinct integers and a target sum, return all possible combinations of numbers that sum to the target.

Approach

  1. Backtracking: We can use backtracking to explore all potential combinations. We’ll start with an empty combination and progressively build it by adding numbers from the list.
  2. Recursive Function: This function will take the current combination, the remaining target, and the starting index in the list to avoid duplicates and control which numbers can be added next.
  3. Base Case: If the remaining target is zero, it means the current combination sums to the target, and we can store it. If it becomes negative, we backtrack.

C# Implementation

Here’s how you can implement the Combination Sum problem in C#:

using System;
using System.Collections.Generic;

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

    private void Backtrack(int[] candidates, int target, List<int> combination, IList<IList<int>> result, int start)
    {
        if (target == 0)
        {
            // Found a valid combination
            result.Add(new List<int>(combination));
            return;
        }

        if (target < 0)
        {
            // Exceeded the target, no need to continue
            return;
        }

        for (int i = start; i < candidates.Length; i++)
        {
            combination.Add(candidates[i]); // Choose the current number
            Backtrack(candidates, target - candidates[i], combination, result, i); // Not i + 1 because we can reuse the same number
            combination.RemoveAt(combination.Count - 1); // Backtrack
        }
    }
}

Explanation of the Code

  1. CombinationSum Method:

    • Initializes a list to hold the result and a list for the current combination.
    • Calls the Backtrack method with the initial parameters.

  2. Backtrack Method:

    • Base Case: If target is zero, we have a valid combination, so we add a copy of combination to the result list.
    • If target is less than zero, we simply return as we can’t make a valid combination.
    • The for loop iterates through the candidates starting from the start index to avoid using previous candidates, allowing for repeated usage.
    • Adds the current candidate to the combination and recursively calls Backtrack, reducing the target by the current candidate.
    • After the recursive call, it removes the last added candidate to backtrack and explore the next candidate.

Complexity

  • Time Complexity: O(2^(target/min(candidates))) in the worst case, where you might explore all combinations.
  • Space Complexity: O(target/min(candidates)) for storing combinations.

Example

Given the input candidates = [2, 3, 6, 7] and target = 7, the output will be:

[
    [2, 2, 3],
    [7]
]

This means that there are two combinations of numbers from the list that sum to 7: [2, 2, 3] and [7].

This backtracking approach efficiently explores all combinations while managing state and ensuring that we only build valid combinations that can reach the target.