ある金額になるコインの組み合わせ

• ref:http://d.hatena.ne.jp/fumokmm/20110813/1313196903

こんなんかな。

coinCombinations :: Int -> [Int] -> [[Int]]
coinCombinations total coins
  | total == 0    = [[]]
  | null coins    = []
  | total < first = firstUnusedList
  | otherwise     = firstUsedList ++ firstUnusedList
      where
        first           = head coins
        firstUsedList   = (map (first:) (coinCombinations (total - first) coins))
        firstUnusedList = coinCombinations total (tail coins)

Python だと Generator ですかね。

def coinCombinations(total, coins):
    if total == 0:
        yield []
        return
    elif not coins:
        return

    for pattern in coinCombinations(total, coins[1:]):
        yield pattern

    if total >= coins[0]:
        for pattern in coinCombinations(total - coins[0], coins):
            yield coins[0:1] + pattern