use std::option::Option;

// Returns Some(nCk) if nCk <= num, None, otherwise
fn exceeds(n: usize, k: usize, num: usize) -> Option<usize> {
    if n <= k || k == 0 {
        return Some(1);
    }

    let sub = match exceeds(n-1,k-1, num) {
        None => return None,
        Some(x) if x > num => return None,
        Some(x) => x,
    };

    match exceeds(n-1,k, num) {
        None => None,
        Some(x) if x + sub > num => None,
        Some(x) => Some(sub + x),
    }
}

fn main() {
    let mut sum = 0;
    for n in 1..(100+1) {
        let mut combinations_under =
            (0..n).map(|k| exceeds(n, k, 1_000_000))
                .take_while(|x| x.is_some())
                .count();

        if combinations_under < n {
            // We skipped the last half of combinations with the `.take_while`
            combinations_under *= 2;
        }

        println!("{} has {} combinations under 1,000,000", n, combinations_under);
        sum += combinations_under;
    }
    println!("Total combinations: {}", sum);
}