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

Question

Есть некоторый массив чисел:

int[] arr = new int[] { 2, 3, 3, 3, 5, 4, 7};

Так жесть искомое число: 9

Каким образом можно найти суммы чисел из чисел в массиве? Вот пример результата : 2, 7, 3, 3, 3, 5, 4, 2, 4, 3. В алгоритмах у меня всё очень плохо и поэтому не знаю даже что загуглить, в какую сторону смотреть?

Answer 1

Этот вариант печатает некоторые разложения несколько раз если в массиве несколько одинаковых чисел:

using System;

void sums(int[] arr, int target) {
    int[] stack = new int[arr.Length];
    int top = 0;

    void iter(int i, int target) {
        if (target < 0) {
            return;
        }
        if (target == 0) {
            for (int j = 0; j < top; ++j) {
                Console.Write(stack[j] + " ");
            }
            Console.WriteLine();
            return;
        }
        if (i < arr.Length) {
            stack[top++] = arr[i];
            iter(i + 1, target - arr[i]);
            --top;
            iter(i + 1, target);
        }
    }

    iter(0, target);
}

sums(new int[] {2, 3, 3, 3, 5, 4, 7}, 9);

$ csc -nologo temp.cs && mono temp.exe
2 3 4 
2 3 4 
2 3 4 
2 7 
3 3 3 
5 4

P.S. Нет опыта с C#. Возможно, я наделал глупостей.

БЛОГ НА HUSL

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

Ответы (1 шт):