leetcode

commit d9f1632a2059b11d4ccd2ca4e846cdf20a8f14ae
parent 37ee7d5b44d16b5134a6b64ef9f8a0f6faab595f
Author: AndrewLockVI <andrewlaack1@gmail.com>
Date:   Sun, 21 May 2023 00:39:08 -0500

Completed path sum iii using dart, dp, recursion, and memoization

Diffstat:
A
path-sum-iii/path-sum-iii.dart
 | 
55
+++++++++++++++++++++++++++++++++++++++++++++++++++++++

1 file changed, 55 insertions(+), 0 deletions(-)
diff --git a/path-sum-iii/path-sum-iii.dart b/path-sum-iii/path-sum-iii.dart
@@ -0,0 +1,55 @@
+//Given the root of a binary tree find all permutations of the binary tree that add up to 
+//a given number and return that value. To do this I used recursion,
+//dynamic programming, and memoization to create branches for each node.
+//Time: 1612ms Beats: 100%
+//Memory: 168.9MB Beats: 100%
+//To improve on this I will incorporate more memoization to make
+//all explored nodes be memoized thus cutting on time.
+class Solution {
+  int? original_val;
+  Map<TreeNode? , List<int>> vals = {};
+  int pathSum(TreeNode? root, int targetSum) {
+    return(get_paths(root,targetSum,0));
+  }
+int get_paths(TreeNode? root, int targetSum, int depth){
+    if(vals.containsKey(root)){
+      List<int> depth_list = (vals[root] ?? []);
+      if(depth_list.contains(depth)){
+        return 0;
+      }
+    }
+    if(original_val == null){
+      original_val = targetSum;
+    }
+    if(root == null){
+        return 0;
+    }
+    int paths = 0;
+    if(targetSum == root.val){
+      if(vals[root] != null){
+        if((vals[root]?.contains(depth)) ?? false){
+          paths += 0;
+        }
+        else{
+          paths += 1;
+          vals[root]?.add(depth);
+        }
+      }
+      else{
+        paths += 1;
+        vals[root] = [depth];
+      }
+    }
+    if(targetSum != (original_val ?? 0)){
+      paths += get_paths(root.left , targetSum - root.val, depth + 1);
+      paths += get_paths(root.right , targetSum - root.val, depth + 1);
+    }
+    else{
+      paths += get_paths(root.left , (original_val ?? 0), 0);
+      paths += get_paths(root.right , (original_val ?? 0) , 0);
+      paths += get_paths(root.left , targetSum - root.val , depth + 1);
+      paths += get_paths(root.right , targetSum - root.val, depth + 1);
+    }
+    return paths;
+  }
+}