Исправить решение для перебора монеты

Понимание проблемы размена монет:

Предполагая, что вы имеете в виду проблему расчета сдачи с наименьшим количеством монет, ключевая идея здесь состоит в том, чтобы думать о проблеме как о выборе на каждом шаге — в данном случае это «какую монету выдать следующей?»

Вы можете разбить задачу на coin_change(score) = 1 + min{coin_change(score - c1), coin_change(score - c2), ...}, где c1, c2... — количество монет, которые у вас есть.

Отслеживание путей:

Это довольно просто. Вместо того, чтобы возвращать решение (минимальная комбинация монет), просто верните все возможности (все комбинации монет). Итак, когда вы делаете рекурсивный вызов, скажем, (score-c1), вы получаете все комбинации монет, которые составляют (score-c1), и вы просто добавляете к ним c1.

Код

coins = [2, 3, 7]
change = 12

def coin_change(c):
  if c == 0:
    return [[]]     # the only combo possible is no coins
  if c < 0:
    return []      # no combos possible
  else:
    all_combos = []
    for i in coins:
      recursive_result = coin_change(c-i)
      for combo in recursive_result:
        combo.append(i)
      all_combos.extend(recursive_result)

    return all_combos

result = coin_change(change)
for combo in result:
  print(combo)

Примечание: это даст вам все перестановки. Если порядок не имеет значения, вы можете использовать наборы для удаления дубликатов.

Изменить: после комментариев приведен код, который удаляет дубликаты

coins = [2, 3, 7]
change = 12

def removeDuplicates(combos):
  filtered = set()
  for combo in combos:
    combo.sort()
    filtered.add(tuple(combo))
  return [list(i) for i in filtered]

def coin_change(c):
  if c == 0:
    return [[]]     # the only combo possible is no coins
  if c < 0:
    return []      # no combos possible
  else:
    all_combos = []
    for i in coins:
      recursive_result = coin_change(c-i)
      for combo in recursive_result:
        combo.append(i)
      all_combos.extend(recursive_result)

    return removeDuplicates(all_combos)

result = coin_change(change)
for combo in result:
  print(combo)

Вот пример, чтобы получить все пути для монет. В общем, когда вы пишете рекурсивную функцию, вы хотите: 1) иметь условие выхода из рекурсии и 2) написать, как расширить предыдущий рекурсивный шаг.

coins  = [2, 3, 7]
change = 12

def coin_change_paths(paths):
    if all(sum(path)>=change for path in paths):
        return paths
    new_paths = []
    for path in paths:
        if sum(path)<change:
            new_paths.extend(path+[c] for c in coins)
        else:
            new_paths.append(path)
    return coin_change_paths(new_paths)

paths = coin_change_paths([[2],[3],[7]])

Это не учитывает дублирование. Для этого вы должны отсортировать, а затем дедуплицировать:

paths = [sorted(p) for p in paths]
temp = []
for p in paths:
    if p not in temp:
        temp.append(p)
paths = temp

Вы все еще должны проверить, какие из них действительны.

paths = [p for p in paths if sum(p)==change]
print(paths)

Попробуйте посмотреть, сможете ли вы объединить их вместе и упростить код.

Другой возможный подход — использовать функцию рекурсивного генератора с yield и yield from. Это избавляет от необходимости сохранять обнаруженные комбинации в списке, который потом нужно вернуть:

coins = [2, 3, 7]
change = 12
def coin_change(c = []):
  if sum(c) == change:
     yield tuple(sorted(c))
  else:
     for i in coins:
        if sum(c+[i]) <= change:
           yield from coin_change(c+[i])

print(list(map(list, set(coin_change()))))

Выход:

[[3, 3, 3, 3], [2, 2, 2, 3, 3], [2, 3, 7], [2, 2, 2, 2, 2, 2]]