Namaran

Code daily. Without assist.

2026-11-01

coins.rs

fn ways(coins: &[u32], rest: u32) -> u32 {
    if rest == 0 {
        return 1;
    }
    coins
        .iter()
        .enumerate()
        .take_while(|&(_, &c)| c <= rest)
        .map(|(i, &c)| ways(&coins[i + 1..], rest - c))
        .sum()
}

fn main() {
    println!("{}", ways(&[1, 2, 3, 4], 5));
    println!("{}", ways(&[4, 3, 2, 1], 5));
}

これは何を出力するでしょうか?

Answer

2 と 1 の2行です。

ways は、coins の中から硬貨を重複なく選んで、合計がちょうど rest になる選び方を数えます。硬貨を1枚選んだら、その後ろの硬貨だけを残して残りの額で数え直します。take_while は、条件が偽になる最初の要素で反復を終え、それより後ろの要素は見ません。偽になった要素を飛ばして次へ進む filter とはそこが違います。

[1, 2, 3, 4] は昇順なので、額を超える硬貨が出たら、その後ろの硬貨もすべて額を超えます。打ち切っても数え漏れはなく、合計5になる {1, 4} と {2, 3} の2通りが数えられます。

[4, 3, 2, 1] では、最初に4を選ぶと残りは [3, 2, 1] で、額は1です。先頭の3が1を超えるので take_while はそこで終わり、後ろにある1を見ないまま0を返します。{4, 1} は数えられず、残る {3, 2} の1通りだけになります。take_while を filter と同じに読むと、2行目も 2 と答えます。