#!/usr/bin/env python3
 
import math
 
def rozměň_a_ukaž(částka, mince):
   # dva možné koncové kroky rekurze
   if částka == 0:
      return 0, [[]]
   elif mince == ():
      return math.inf, [[]]
   # nadále nepoužitelná mince
   elif mince[0] > částka:
      return rozměň_a_ukaž(částka, mince[1:])
   # minci je možno použít
   else:
      # větev, kde minci použijeme
      ano_mincí, ano_mince = rozměň_a_ukaž(částka - mince[0], mince)
      ano = ano_mincí + 1, [x + [mince[0]] for x in ano_mince]
      # větev, kde minci nepoužijeme
      ne = rozměň_a_ukaž(částka, mince[1:])
      # výběr lepší větve výpočtu
      if ano[0] < ne[0]:
         return ano
      elif ano[0] > ne[0]:
         return ne
      else:    # obě větve jsou srovnatelné, tj. ano[0] == ne[0]
         return ano[0], ano[1] + ne[1]
 
# 2 řešení
řešení = rozměň_a_ukaž(12, (5, 4, 2, 1))     # (3, [[2, 5, 5], [4, 4, 4]])
print(řešení)
 
# 5 řešení
řešení = rozměň_a_ukaž(36, (8, 7, 6, 5, 4, 3, 2, 1))
print(řešení)