Найти все комбинации заданного набора целых чисел, суммирующихся до заданной суммы

Question

Я ищу ответ на следующую проблему.

Учитывая набор целых чисел (без дубликатов) и сумму, найдите все возможные комбинации элементов набора, суммирующихся до суммы. Порядок решений не имеет значения (решения {2, 2, 3} и {3, 2, 2} равны).

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

Пример: Набор {2,3,5} Сумма 10

Результат: {2, 2, 2, 2, 2}, {2, 2, 3, 3}, {2, 3, 5}, {5, 5}

Я рассмотрел проблему Subset Sum, а также проблему изменения монет, но не смог ее адаптировать в соответствии с моими потребностями. Я не очень хорошо знаком с динамическим программированием, поэтому, вероятно, это возможно, но я не мог понять.

Поскольку я имею дело с довольно большим набором элементов (около 50), предварительная вычисление всех наборов не является вариантом, так как это займет очень много времени. Предпочтительным способом (если это возможно) было бы предпочтительнее вытащить различные решения из таблицы подмножества.

Любые советы, советы или образцы кода будут оценены!

Answer 1

сложность

Решение:

• Время: О (п * М)
• память: О (М),

, где М представляет собой значение суммы, п устанавливается размер

int numberOfSums(Set<Integer> values, int sum) { 
    // sumCount[i] -> number of ways to get sum == i 
    int sumCount[] = new int[sum+1]; 
    sumCount[0] = 1; 
    for(int v : values) { 
     for(int i=0; i<=sum-v; ++i) 
      sumCount[i+v] += sumCount[i]; 
    } 
    return sumCount[sum]; 
} 

Answer 2

Вот функция Haskell, которая вычисляет ответ:

partitions 0 xs = [[]] 
partitions _ [] = [] 
partitions n (xxs@(x:xs)) | n < 0 = [] 
          | otherwise = (map (x:) (partitions (n-x) xxs)) ++ partitions n xs 

Примеры:

*Main> partitions 1 [1] 
[[1]] 
*Main> partitions 5 [1..5] 
[[1,1,1,1,1],[1,1,1,2],[1,1,3],[1,2,2],[1,4],[2,3],[5]] 
*Main> length $ partitions 10 [1..10] 
42 
*Main> length $ partitions 20 [1..20] 
627 
*Main> length $ partitions 40 [1..40] 
37338 
*Main> partitions 10 [1,2,4] 
[[1,1,1,1,1,1,1,1,1,1],[1,1,1,1,1,1,1,1,2],[1,1,1,1,1,1,2,2],[1,1,1,1,1,1,4],[1,1,1,1,2,2,2],[1,1,1,1,2,4],[1,1,2,2,2,2],[1,1,2,2,4],[1,1,4,4],[2,2,2,2,2],[2,2,2,4],[2,4,4]] 

Semi-live demo

Answer 3

Это известно как Change-making problem и является классическим примером в dynamic programming.

Некоторые ранние ответы подсчитали общее количества решений, в то время как вопрос попросил перечисления из возможных решений.

Вы не отметили свой вопрос на языке, так что вот реализация в Python. Адаптируйте его к любому языку, который вам нравится, используя тип данных «сумка» вашего языка (n.b. Counter - это «сумка» Python).

from collections import Counter 

def ways(total, coins): 
    ways = [[Counter()]] + [[] for _ in range(total)] 
    for coin in coins: 
     for i in range(coin, total + 1): 
      ways[i] += [way + Counter({coin: 1}) for way in ways[i-coin]] 
    return ways[total] 

Выходной тип данных - это список мешков. Демо-использование для их печати:

>>> from __future__ import print_function # for Python 2 compatibility 
>>> for way in ways(total=10, coins=(2,3,5)): 
...  coins = (coin for coin,count in way.items() for _ in range(count)) 
...  print(*coins) 
... 
2 2 2 2 2 
2 2 3 3 
2 3 5 
5 5