Поиск всех возможных комбинаций чисел для достижения заданной суммы с нулями и повторениями

Question

Я знаю, что есть много постов с способами генерирования подмножества элементов, которые генерируют сумму заданного числа, но ни один из них не делает то, что мне нужно.По крайней мере, не в C #.

Мне нужны все комбинации чисел в данном массиве, которые суммируются до заданного числа.

Например, в массиве a = {0,1,2,3,4,5,6,7,8,9), чтобы получить число N = 56, следует вернуть, среди всех вариантов, также список «8,8,8,8,8,8,8" .Большинство алгоритмов, которые я нахожу, не допускают повторений в результате, а те, которые допускают, не находятся в C #.

Это очень полный поток, но он не содержит нулей. Поиск всех возможных комбинаций чисел для достижения заданной суммы Вот версия решения на C #, описанная в посте выше.

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);
   }
}

Кто-нибудь знает, что нужно сделать, чтобы достичьЭто?В приведенном выше примере, что можно изменить, чтобы разрешить повторения?

Answer 1

Это просто.Все, что вам нужно, это заменить i + 1 на i в последнем for ().Окончательный код будет:

    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);
        }
    }

Я также добавил проверки на ноль и целевое значение