Counting Change Combinations

計算出所有找零的可能組合數量

Keyo
mis101247
2 min readSep 14, 2018

--

此題連結
https://www.codewars.com/kata/541af676b589989aed0009e7

題目說明

假設要找回6元 零錢的種類有1, 2, 5元這三種
那可能組合就是
1, 1, 1, 1, 1, 1
2, 2, 2
2, 2, 1, 1
2, 1, 1, 1, 1
5, 1

Ans: 共5種可能

解法說明:

解法有很多種,像我第一次看到這題目就是用超暴力的遞迴來解,有解出來但timeout不給過就想很久,最後直接去問google大神,有很多演算法以下是我學到的

假設要找回10元 零錢的種類有2, 3, 5元這三種
那我們就先創出array index 0~10,

公式 if (coin >= arr[index] ) arr[index] += arr[index-coin]

如果有其他解法歡迎分享◟( •ω• )◞

--

--

Keyo
mis101247

目前在荷蘭打工度假,於一間新創擔任FullStack。喜歡學習嘗試新事物,所學不侷限於目前職業所需的知識。