Rustで再帰関数 (4)

『アルゴリズムとデータ構造』を Rust で実装してみるシリーズ。4章の再帰と分割統治法。

前回 → https://quantized-cube.com/rust-recursive-03

今回は 部分和問題。

use proconio::input;

fn input(use_default_values: bool) -> (usize, u64, Vec<u64>) {
    if use_default_values {
        let n = 4;
        let w = 14;
        let a = vec![3, 2, 6, 5];
        return (n, w, a);
    } else {
        println!("Input n and a:");
        input! {
            n: usize,
            w: u64,
            a: [u64; n],
        }
        return (n, w, a);
    }
}

fn func(i: usize, w: i64, a: &Vec<u64>) -> bool {
    // ベースケース
    if i == 0 {
        if w == 0 {
            return true;
        } else {
            return false;
        }
    }

    // a[i - 1] を選ばない場合
    if func(i - 1, w, a) {
        return true;
    }

    // a[i - 1] をぶ場合
    if func(i - 1, w - a[i - 1] as i64, a) {
        return true;
    }

    // どちらも false の場合は false
    return false;
}

/// 部分和問題を再帰関数を用いる全探索で解く
pub fn code_4_9(use_default_values: bool) -> String {
    // 入力
    let (n, w, a) = input(use_default_values);

    // 再帰的に解く
    if func(n, w as i64, &a) {
        String::from("Yes")
    } else {
        String::from("No")
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn code_4_9_works() {
        assert_eq!(code_4_9(true), String::from("Yes"));
    }
}

GitHub のリポジトリはこちら https://github.com/quantized-cube/book_algorithm_solution_rust