leetcode

commit eca5bf6fddad624cc8909c8ff9b0cfae8910f046
parent 238de164eaeb14e5634fbd1904a81417b3440303
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Thu, 16 Feb 2023 14:24:58 +0100

LeetCode 75 II: Day 13

Diffstat:
A
Problems/0416.cpp
 | 
15
+++++++++++++++
M
README.md
 | 
1
+

2 files changed, 16 insertions(+), 0 deletions(-)
diff --git a/Problems/0416.cpp b/Problems/0416.cpp
@@ -0,0 +1,15 @@
+class Solution {
+public:
+  bool canPartition(vector<int> &nums) {
+    int sum = accumulate(nums.begin(), nums.end(), 0), hsum = sum / 2;
+    if (sum % 2) return false;
+    vector<bool> dp(hsum + 1, false);
+
+    dp[0] = true;
+    for (int num : nums)
+      for (int j = hsum; j >= num; j--)
+        if (dp[j - num]) dp[j] = true;
+
+    return dp.back();
+  }
+};
diff --git a/README.md b/README.md
@@ -216,6 +216,7 @@ for solving problems.
 |  0413  |   Medium   | [Arithmetic Slices](Problems/0413.cpp)                                                           |
 |  0414  |    Easy    | [Third Maximum Number](Problems/0414.cpp)                                                        |
 |  0415  |    Easy    | [Add Strings](Problems/0415.cpp)                                                                 |
+|  0416  |   Medium   | [Partition Equal Subset Sum](Problems/0416.cpp)                                                  |
 |  0417  |   Medium   | [Pacific Atlantic Water Flow](Problems/0417.cpp)                                                 |
 |  0424  |   Medium   | [Longest Repeating Character Replacement](Problems/0424.cpp)                                     |
 |  0429  |   Medium   | [N-ary Tree Level Order Traversal](Problems/0429.cpp)                                            |