leetcode

commit 9212a087df08586dd7c8c525297ad0271cbe2087
parent c7a3c05c4531c60d82027c7f995e5651c93d86f8
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Wed,  4 Dec 2024 15:44:42 +0100

1 Random Problem

Diffstat:
A
Problems/0698.cpp
 | 
72
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 73 insertions(+), 0 deletions(-)
diff --git a/Problems/0698.cpp b/Problems/0698.cpp
@@ -0,0 +1,72 @@
+class Solution {
+  public:
+    bool canPartitionKSubsets(vector<int> &nums, int k) const {
+        int acc = 0;
+
+        for (const int n : nums)
+            acc += n;
+        if (acc % k) return false;
+
+        const int goal = acc / k;
+
+        sort(rbegin(nums), rend(nums));
+        if (nums[0] > goal) return false;
+
+        const function<bool(uint16_t, int, int, int)> rec = [&](uint16_t visited, int left, int sum,
+                                                                int start) {
+            if (sum == goal) left--, sum = 0, start = 0;
+            if (left == 1) return true;
+
+            for (int i = start; i < size(nums); i++) {
+                const uint16_t mask = 1 << i;
+                if (visited & mask) continue;
+                if (sum + nums[i] > goal) continue;
+
+                if (rec(visited | mask, left, sum + nums[i], i + 1)) return true;
+                if (sum == 0) return false;
+            }
+
+            return false;
+        };
+
+        return rec(1, k, nums[0], 1);
+    }
+};
+
+class Solution {
+  public:
+    bool canPartitionKSubsets(vector<int> &nums, int k) const {
+        static int acc[16];
+        int sum = 0;
+
+        for (const int n : nums)
+            sum += n;
+        if (sum % k) return false;
+
+        const int goal = sum / k;
+
+        sort(rbegin(nums), rend(nums));
+        if (nums[0] > goal) return false;
+
+        memset(acc, 0x00, sizeof(acc));
+        acc[0] = nums[0];
+
+        function<bool(int)> rec = [&](int crnt) {
+            if (crnt == size(nums)) return true;
+
+            for (int i = 0; i < k; i++) {
+                if (acc[i] + nums[crnt] > goal) continue;
+
+                acc[i] += nums[crnt];
+                if (rec(crnt + 1)) return true;
+                acc[i] -= nums[crnt];
+
+                if (acc[i] == 0) return false;
+            }
+
+            return false;
+        };
+
+        return rec(1);
+    }
+};
diff --git a/README.md b/README.md
@@ -535,6 +535,7 @@ reference and a base for solving problems.
 |  0690  |   Medium   | [Employee Importance](Problems/0690.cpp)                                                           |
 |  0692  |   Medium   | [Top K Frequent Words](Problems/0692.cpp)                                                          |
 |  0695  |   Medium   | [Max Area of Island](Problems/0695.cpp)                                                            |
+|  0698  |   Medium   | [Partition to K Equal Sum Subsets](Problems/0698.cpp)                                              |
 |  0699  |    Hard    | [Falling Squares](Problems/0699.cpp)                                                               |
 |  0700  |    Easy    | [Search in a Binary Search Tree](Problems/0700.cpp)                                                |
 |  0701  |   Medium   | [Insert into a Binary Search Tree](Problems/0701.cpp)                                              |