1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
|
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
}
}
|
