fn main() {
    println!("Hello, world!");
    let tests = [
        (vec![1,2,3], 4, 7),
        // (vec![9], 3, 0),
        (vec![2,1,3], 35, 1_132_436_852),
        // (vec![10,20,30,40,50,60,70,80,90,100,110,120,130,140,150,160,170,180,190,200,210,220,230,240,250,260,270,280,290,300,310,320,330,340,350,360,370,380,390,400,410,420,430,440,450,460,470,480,490,500,510,520,530,540,550,560,570,580,590,600,610,620,630,640,650,660,670,680,690,700,710,720,730,740,750,760,770,780,790,800,810,820,830,840,850,860,870,880,890,900,910,920,930,940,950,960,970,980,990,111], 999, 2)
    ];

    for test in tests {
        println!("{:?} {} is {} should be {}",
            test.0, test.1,
            Solution::combination_sum4(test.0.clone(), test.1),
            test.2
                 );
    }
}
struct Solution {}


impl Solution {
    pub fn combination_sum4(nums: Vec<i32>, target: i32) -> i32 {
        let mut cache = vec![0; target as usize];
        Solution::combination_sum4_from(&nums, 0, target, &mut cache)
    }

    pub fn combination_sum4_from(nums: &Vec<i32>, from: i32, target: i32, cache: &mut Vec<i32>) -> i32 {
        if from > target {return 0};
        if from == target {return 1};
        if cache[from as usize] > 0 {return cache[from as usize];}

        let result = nums.iter().rev().map(|x| Solution::combination_sum4_from(&nums, from + x, target, cache)).sum();
        cache[from as usize] = result;
        println!("{:?}", cache);
        result
    }
}