Все комбинации, которые равны или превышают заданное число

Обновленный ответ

В вопрос добавлены дополнительные сведения о требованиях. Я думаю, что эта версия соответствует им. Но ожидаемая структура вывода не была указана, так что это предположение. Это заканчивается массивом результатов, подобных этому:

{initial: {a: 1, b: 2, c: 1}, last: {d: 3}}

или вот так:

{initial: {b: 2, c: 1, e: 2}}

Он делает это, сначала находя все подмножества начальных значений вместе с их дополнениями, используя функцию partitions. partitions (['a', 'b', 'c', 'd']) будет иметь шестнадцать элементов, включая [['a', 'b', 'd'], ['c']], [['b', 'd'], ['a', 'c']] и [[], ['a', 'b', 'c', 'd']].

Затем для каждого раздела, если его сумма левой половины равна цели, мы включаем его. Если сумма меньше целевого значения, мы включаем результат для каждого значения в правой половине, которое превышает целевое значение.

Вот реализация в Javascript:

// utility functions
const last = (xs) => 
  xs [xs .length - 1]

const partitions = (xs) => 
  xs .length === 0
    ? [[[], []]]
    : partitions (xs .slice (0, -1)) .flatMap (([p, q]) => [ 
        [[...p, last (xs)], q], 
        [p, [...q, last (xs)]] 
      ])

// helper function
const total = (xs) =>
  xs .reduce ((a, [k, v]) => a + v, 0)


// main function
const sumTo = (n, xs, parts = partitions (xs)) =>
  parts .flatMap (([incl, excl], _, __, t = total (incl)) => [
    ... (t == n ? [{initial: incl}] : []),
    ... (t < n
           ? excl .filter (([k, v]) => v + t > n) 
                  .map (e => ({initial: incl, last: [e]}))
           : []
        )
  ])


// public function
const subsetSum = (n, dict) =>
  sumTo (n, Object.entries (dict))
    .map (({initial, last}) => ({
      initial: Object .fromEntries (initial), 
      ... (last ? {last: Object .fromEntries (last)} : {})
    }))


// sample data
const dict = {a: 1, b: 2, c: 1, d: 3, e: 2}


// demo
console .log (subsetSum (5, dict))

.as-console-wrapper {max-height: 100% !important; top: 0}

Начнем с тривиальной вспомогательной функции last, которая просто выбирает последний элемент массива. Далее имеем partition, уже описанный выше. Наша основная функция — sumTo, которая выполняет описанную работу. Его входными данными являются целевое число и структура, подобная [['a', '1], ['b', 2'], ['c', 1], ['d', 3], ['e', 2]], которую легко получить из словаря, но с которой проще работать. Он возвращает объект с двумя свойствами, например {initial: [['a', 1], ['b', 2], ['c', 1]], last: [['d', 3]]}. Наконец, у нас есть общедоступная функция subsetSum, которая преобразует формат словаря во входные данные, необходимые для sumTo, а затем преобразует результат обратно в выходной формат. Это было бы легко исправить, чтобы создать любой формат вывода, который вам нужен.

Немного отформатировав вывод, мы можем увидеть наши результаты более просто:

subsetSum  (5, dict)
  .map (({initial, last}) => 
      Object .keys (initial) .join ('') +
      (last ? '-' + Object .keys (last) .join ('') : '')
  )
//=> ["abc-d", "abc-e", "abe", "ab-d", "acd", "ace-b", 
//    "ace-d", "ad-b", "ad-e", "ae-d", "bce", "bc-d", 
//    "bd", "be-d", "cd-b", "cd-e", "ce-d", "de"]

Это, вероятно, неэффективно. У меня нет реального представления о вероятных закономерностях роста проблемы. Но этот алгоритм экспоненциален по размеру словаря, и для этого метода нет другого пути, поскольку проблема подмножества, лежащая в основе partitions, дает 2 ^ n результатов.

Но это может быть отправной точкой для сравнения с другими решениями.

Оригинальный ответ

Если все порядки имеют значение (и меня смущают детали этого требования), то этот алгоритм должен сделать это, используя список записей, каждый из которых имеет key и value:

if (n <= 0) or if our list of entries is empty,
  return a list containing only the empty string
otherwise return the concatenation of the following lists, one for each entry:
  a recursive call passing 
    - `n - value`
    - the list excluding the current entry,
  with each result being prepended with the current entry's key 

Если вы знакомы с синтаксисом Javascript, то это должно работать:

const excluding = (i) => (xs) =>
  [...xs .slice (0, i), ...xs .slice (i + 1)]

const sumTo = (n, xs) =>
  n <= 0 || xs.length == 0 
    ? ['']
    : xs .flatMap (
        ([k, v], i) => sumTo (n - v, excluding (i) (xs)) .map (r => k + r)
      )
  
const subsetSum = (n, dict) => 
  sumTo (n, Object .entries (dict))

const dict = {a: 1, b: 2, c: 1, d: 3, e: 2}

console .log (subsetSum (5, dict))

.as-console-wrapper {max-height: 100% !important; top: 0}

Трудно представить, что порядок может быть совершенно неуместным, поскольку 'cde' должно подойти, а 'dec' — нет. Но я не понимаю идею о том, что порядок имеет значение только тогда, когда общая сумма превышает цель. Можете ли вы объяснить более полно?

Я думаю, что изменение алгоритма обмена монет, подобное этому, решает проблему.

import itertools
def subset_sum(numbers, target, partial=[]):
    exceed = sum([ v for k, v in partial[:-1]])
    s = sum([ v for k, v in partial])
    if exceed >= target:
        return
    elif s == target: 
        print (partial,sum([ v for k, v in partial]), target)
    elif s > target:
        print("print all permutation")
        p = list(itertools.permutations(partial))
        for state in p:
            legit = sum([v for k, v in state[:-1]])
            if (legit < target):
                print(state)

    for i in range(len(numbers)):
        k, v = numbers[i]
        remaining = numbers[i+1:]
        subset_sum(remaining, target, partial + [(k,v)])

if __name__ == "__main__":
    subset_sum([('a',1),('b',2),('c',1),('d',3),('e',2)],5)