0

I know there are plenty of posts with ways to generate a subset of items that generates a sum of a given number, but none of them do what I need. At least not in C#.

I need all the combinations of the numbers in a given array, that sum up to a given number.

For example, in the array a = {0,1,2,3,4,5,6,7,8,9), to get a number N = 56, it should return, among all the options, also the list "8,8,8,8,8,8,8". Most of the algorithms I find don't allow repetitions in the result, and the ones that do, are not in C#.

This one is a very complete thread, but it doesn't include the zeros. Finding all possible combinations of numbers to reach a given sum Here's the C# version of the solution, described in the post above.

public static void Main(string[] args)
{
    List<int> numbers = new List<int>() { 3, 9, 8, 4, 5, 7, 10 };
    int target = 15;
    sum_up(numbers, target);
}

private static void sum_up(List<int> numbers, int target)
{
    sum_up_recursive(numbers, target, new List<int>());
}

private static void sum_up_recursive(List<int> numbers, int target, 
 List<int> partial)
{
   int s = 0;
   foreach (int x in partial) s += x;

   if (s == target)
       Console.WriteLine("sum(" + string.Join(",", partial.ToArray()) + ")=" + target);

   if (s >= target)
       return;

   for (int i = 0; i < numbers.Count; i++)
   {
       List<int> remaining = new List<int>();
       int n = numbers[i];
       for (int j = i + 1; j < numbers.Count; j++) remaining.Add(numbers[j]);

       List<int> partial_rec = new List<int>(partial);
       partial_rec.Add(n);
       sum_up_recursive(remaining, target, partial_rec);
   }
}

Does anyone know what needs to be done to achieve it? In the example above, what could be changed to allow repetitions?

Uwe Keim
  • 39,551
  • 56
  • 175
  • 291
Evellyn Mascarenhas
  • 1

1 Answers1

0

That's easy. All you need is change i+1 to i in the last for(). The final code will be:

    public static void Main(string[] args)
    {
        List<int> numbers = new List<int>() {0, 3, 4, 5, 6, 7, 8, 9 };
        int target = 2;
        sum_up(numbers, target);
        Console.ReadLine();
    }

    private static void sum_up(List<int> numbers, int target)
    {
        if (numbers.Min() > target || target < 1)
        {
            Console.WriteLine("There is no solution!");
            return;
        }
        if (numbers.Contains(0))
        {
            Console.WriteLine("There are infinite number of solutions!");
            return;
        }

        sum_up_recursive(numbers, target, new List<int>());
    }

    private static void sum_up_recursive(List<int> numbers, int target,
     List<int> partial)
    {
        int s = 0;
        foreach (int x in partial) s += x;

        if (s == target)
            Console.WriteLine("sum(" + string.Join(",", partial.ToArray()) + ")=" + target);

        if (s >= target)
            return;

        for (int i = 0; i < numbers.Count; i++)
        {
            List<int> remaining = new List<int>();
            int n = numbers[i];
            for (int j = i; j < numbers.Count; j++) remaining.Add(numbers[j]);

            List<int> partial_rec = new List<int>(partial);
            partial_rec.Add(n);
            sum_up_recursive(remaining, target, partial_rec);
        }
    }

I also added checks for zero and target value

Aleksandr Morkovin
  • 119
  • 1
  • 6