leetcode

commit 98ea5452cf3ca3812f21159d9261d5d057124fbb
parent 30a918e9bbac48f4e0ec30ab537afe974ada0774
Author: AndrewLockVI <andrewlaack1@gmail.com>
Date:   Sun, 28 May 2023 17:21:24 -0500

Completed combination sum iv using dart, dp, recursion, and memoization

Diffstat:
A
combination-sum-iv/combination-sum-iv.dart
 | 
40
++++++++++++++++++++++++++++++++++++++++

1 file changed, 40 insertions(+), 0 deletions(-)
diff --git a/combination-sum-iv/combination-sum-iv.dart b/combination-sum-iv/combination-sum-iv.dart
@@ -0,0 +1,40 @@
+//Given a list of options (nums) where each value is unique
+//and each value can be used as many times as you would like return
+//the number of permutations that can add up to the target value.
+
+//To solve this I used DP and memoization. The first thing
+//to understand is since the nums list will not change as you 
+//recurse you can use a simple memoization technique because you 
+//do not have changing constraints depending on which numbers
+//have been used in the past. Given this each time you run into
+//a target value you can check how many ways that target can become 0
+//if the problem has been done before return the answer if not recurse to find
+//all possible ways to reach 0 from that position with the options in the nums list.
+//Then return the possible ways to do it to the parent. Continue doing this until all 
+//nums have been iterated through and return the final number of satisfying permutations.
+
+//Time: 282ms Beats: 100%
+//Memory: 141.7MB Beats: 100%
+
+class Solution {
+  Map<int,int> memo = {};
+  int combinationSum4(List<int> nums, int target) {
+      if(memo[target] != null){
+          return (memo[target] ?? 0);
+      }
+      if(target <= 0){
+        if(target == 0){
+            return 1;
+        }
+        if(target < 0){
+            return 0;
+        }
+      }
+      int return_val = 0;
+      for(int i = 0 ; i < nums.length ; ++i){
+          return_val += combinationSum4(nums, target - nums[i]);
+      }
+      memo[target] = return_val;
+      return return_val;
+  }
+}