can partition

jhideki · jhideki · commit 1277f3b44368 · 2024-07-04T12:13:00.000-07:00
diff --git a/src/main.rs b/src/main.rs
@@ -1,2 +1,2 @@
-mod longest_inc_sub;
+mod partition_equal_subset;
 fn main() {}
diff --git a/src/partition_equal_subset.rs b/src/partition_equal_subset.rs
@@ -0,0 +1,23 @@
+pub struct Solution {}
+impl Solution {
+    pub fn can_partition(nums: Vec<i32>) -> bool {
+        use std::collections::HashSet;
+        let mut target: i32 = nums.iter().sum();
+        if target % 2 == 0 {
+            target = target / 2;
+        } else {
+            return false;
+        }
+        let mut mem: HashSet<i32> = HashSet::new();
+        mem.insert(0);
+        for i in (0..nums.len()).rev() {
+            if mem.contains(&target) {
+                return true;
+            }
+            for val in mem.clone() {
+                mem.insert(val + nums[i]);
+            }
+        }
+        false
+    }
+}
