leetcode

commit 1af9cba05269900677e23e3bbfedd3b7075e6d30
parent 169da2018133b28e107c19278021dcc449362487
Author: Jack Sangdahl <jack@pngu.org>
Date:   Fri,  7 Nov 2025 08:47:22 -0700

698. partition to k equal sum subsets

Diffstat:
A
partition_k_equal_subset.c
 | 
53
+++++++++++++++++++++++++++++++++++++++++++++++++++++
A
partition_k_equal_subset.py
 | 
46
++++++++++++++++++++++++++++++++++++++++++++++

2 files changed, 99 insertions(+), 0 deletions(-)
diff --git a/partition_k_equal_subset.c b/partition_k_equal_subset.c
@@ -0,0 +1,53 @@
+// 698. Partition to K Equal Sum Subsets
+#include "leetcode.h"
+
+/*
+ * given an integer array 'nums' and an integer 'k', return 'true' if it is
+ * possible to divide this array into 'k' non-empty subsets whose sums are all
+ * equal.
+ */
+
+int cmp(const void *a, const void *b) { return *(int *)b - *(int *)a; }
+
+bool dfs(int *nums, bool *vis, int curr, int n, int k, int group,
+         long long target, long long sum) {
+  if (group == k)
+    return true;
+  if (sum > target)
+    return false;
+  if (sum == target)
+    return dfs(nums, vis, group, n, k, group + 1, target, 0);
+  int prev = -1;
+  for (int i = curr; i < n; i++) {
+    if (vis[i])
+      continue;
+    if (nums[i] == prev)
+      continue;
+    vis[i] = true;
+    if (dfs(nums, vis, i + 1, n, k, group, target, sum + nums[i]))
+      return true;
+    vis[i] = false;
+    prev = nums[i];
+  }
+  return false;
+}
+
+bool canPartitionKSubsets(int *nums, int numsSize, int k) {
+  long long sum = 0;
+  for (int i = 0; i < numsSize; i++)
+    sum += nums[i];
+  if (sum % k)
+    return false;
+  long long target = sum / k;
+  qsort(nums, numsSize, sizeof(int), cmp);
+  if (nums[0] > target)
+    return false;
+  bool vis[16] = {false};
+  return dfs(nums, vis, 0, numsSize, k, 0, target, 0);
+}
+
+int main() {
+  int n1[] = {4, 3, 2, 3, 5, 2, 1}, n2[] = {1, 2, 3, 4};
+  printf("%d\n", canPartitionKSubsets(n1, ARRAY_SIZE(n1), 4)); // expect: 1
+  printf("%d\n", canPartitionKSubsets(n2, ARRAY_SIZE(n2), 3)); // expect: 0
+}
diff --git a/partition_k_equal_subset.py b/partition_k_equal_subset.py
@@ -0,0 +1,46 @@
+# 698. Partition to K Equal Sum Subsets
+
+"""
+given an integer array 'nums' and an integer 'k', return 'true' if it is
+possible to divide this array into 'k' non-empty subsets whose sums are all
+equal.
+"""
+
+
+class Solution(object):
+    def canPartitionKSubsets(self, nums, k):
+        """
+        :type nums: List[int]
+        :type k: int
+        :rtype: bool
+        """
+        total = sum(nums)
+        if total % k:
+            return False
+        target = total // k
+        nums.sort(reverse=True)
+        if nums[0] > target:
+            return False
+        n, memo = len(nums), {}
+
+        def dfs(used, curr):
+            if used == (1 << n) - 1:
+                return True
+            if (used, curr) in memo:
+                return memo[(used, curr)]
+            for i in range(n):
+                if not (used >> i) & 1 and curr + nums[i] <= target:
+                    new = curr + nums[i]
+                    next = 0 if new == target else new
+                    if dfs(used | (1 << i), next):
+                        memo[(used, curr)] = True
+            memo[(used, curr)] = False
+            return False
+
+        return dfs(0, 0)
+
+
+if __name__ == "__main__":
+    obj = Solution()
+    print(obj.canPartitionKSubsets(nums=[4, 3, 2, 3, 5, 2, 1], k=4))
+    print(obj.canPartitionKSubsets(nums=[1, 2, 3, 4], k=3))