2026-11-06
exact_change.rs
fn can_pay(coins: &[u32], price: u32) -> bool {
let n = coins.len();
(0..(1 << n) - 1).any(|mask| {
let sum: u32 = (0..n).filter(|i| mask >> i & 1 == 1).map(|i| coins[i]).sum();
sum == price
})
}
fn main() {
println!("{}", can_pay(&[50, 10, 100], 160));
println!("{}", can_pay(&[50, 10, 100], 60));
}
can_pay は、手持ちの硬貨 coins からいくつかを選び、合計がちょうど price になる選び方があるかを返すつもりの関数です。main のとおり、50円・10円・100円の硬貨で160円と60円を調べると、いまは false と true が表示されます。160円は3枚とも使えば払えるので、本来の出力は true と true です。
Answer
Wrong
(0..(1 << n) - 1).any(|mask| {
mask の i ビット目が1なら coins[i] を選ぶので、n 枚の硬貨の選び方は0から2n − 1 までの2n 個の整数で表されます。Rust の a..b は b を含まない範囲なので、0..(1 << n) - 1 は0から2n − 2 までで終わり、最後の2n − 1 が抜けます。2n − 1 は下から n ビットがすべて1の数で、全部の硬貨を選ぶ選び方です。
硬貨が3枚なら mask は0から6までで、3枚とも使う7(0b111)が試されません。160円になる選び方は 50 + 10 + 100 の1通りだけなので、any は false を返します。60円は50円と10円の mask = 3 で見つかるので、こちらは正しく true です。全部を使う組み合わせが要る入力でだけ結果が変わるので、少ない硬貨で払える例を試しても見つかりません。
Right
(0..1 << n).any(|mask| {
範囲の終わりを 1 << n にすると、.. が終端を含まないので、mask はちょうど0から2n − 1 までの2n 個を回ります。<< は .. より強く結び付くので、括弧は要りません。「最大の mask まで」と書きたいなら、終端を含む 0..=(1 << n) - 1 でも同じ範囲になります。