数学パズル Q5

# 入力：数値
# 出力：組み合わせの数
def ryogae(tar)
  cnt = 0
  (0..15).each do |zyu|
    (0..15).each do |gozyu|
      (0..15).each do |hyaku|
        (0..15).each do |gohyaku|
          next if zyu + gozyu + hyaku + gohyaku > 15
          val = 10 * zyu + 50 * gozyu + 100 * hyaku + 500 * gohyaku
          cnt += 1 if val == tar
        end
      end
    end
  end
  cnt
end

puts ryogae(1000)

配列に硬貨を入れて、重複組合せでチェックするのが一番良さそう。
重複組合せをぱっとは作れないので後回し。
現在の硬貨と次に追加する硬貨で再帰でも作れそう。

追記 再帰バージョン

def ryogae(tar, accCoins = [])
  return 0 if accCoins.sum > tar || accCoins.length > 15
  # 重複があるから弾く、もう少し良いやり方を考えたい
  return 0 if accCoins != accCoins.sort
  return 1 if accCoins.sum == tar

  coins = [10, 50, 100, 500]
  coins.reduce(0) do |acc, cur|
    acc + ryogae(tar, [*accCoins, cur])
  end
end

追記 重複組合せ
上のコード書いたらなんか重複組合せが簡単にできそうだったから書いてみた
配列が深くなってしまったとこがびみょい

# 重複組合せ
def kumi(num, arr, accKumi = [])
  return if accKumi.count > num
  return if accKumi != accKumi.sort
  return accKumi if accKumi.count == num

  arr.reduce([]) do |acc, cur|
    val = kumi(num, arr, [*accKumi, cur])
    val.nil? ? acc : acc.push(val)
  end
end

p kumi(3, [1, 2, 3, 4])

追記
読み返してみたけど、これ何やってんだろう
重複組合せでもない