1 files changed, 37 insertions, 0 deletions
diff --git a/combination-sum-iv/src/main.rs b/combination-sum-iv/src/main.rs
new file mode 100644
index 0000000..b0ee823
--- /dev/null
+++ b/combination-sum-iv/src/main.rs
@@ -0,0 +1,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
+    }
+}