Номера комбинаций могут быть добавлены, чтобы дать определенную сумму

Question

Имея массив целых чисел (например, 3, 4, 5), как вы можете найти все комбинации, которые они могут быть добавлены до заданной суммы? (., Например, 17)

Для примера было бы четыре способа три номера можно добавить до 17:

• 5 + 5 + 4 + 3
• 5 + 4 + 4 + 4
• 5 + 3 + 3 + 3 + 3
• 4 + 4 + 3 + 3 + 3

Как рассчитать это программно? Например. используя javascript.

Answer 1

Общая тема называется «целые разделы». Поиск этого может вызвать алгоритм, который вы можете использовать.

Answer 2

Вот возможное решение (я не претендую на его эффективность, хотя):

1. Вы можете создать структуру данных, которая содержит сумму чисел. (Значение этой суммы и всех чисел, которые ее составляют).
2. У вас есть массив A и целевая сумма TARGET.
3. Вы сортировки массива A.
4. создается новый массив B, инициализированный от А со структурой данных, описанной выше, где каждый элемент B является суммой соответствующего числа в А.
5. В то время как (B имеют значение)
   1. Вы добавляете каждое из чисел в А к структурам данных в B (B теперь будет иметь B.length*A.length элементов)
   2. Каждую сумму в B, который TARGET является решением
   3. каждой суммы в в, по меньшей мере, TARGET удаляется из B

Примечание: Если какая-либо комбинация элементов в A равна 0, программа никогда не закончится (как и ожидалось). Это означает, что A должен иметь все элементы, превышающие 0