aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-04-06 20:14:42 -0600
committerJack Sangdahl <[email protected]>2025-04-06 20:14:42 -0600
commitbeff35cecb8082a45325921e6f97179976808fe6 (patch)
treeeba848b0becff05985bce36009728395d2d8c1bc
parent9b2152674c86116b8a973d7691b239b39f63eb89 (diff)
downloadleetcode-beff35cecb8082a45325921e6f97179976808fe6.tar.gz
leetcode-beff35cecb8082a45325921e6f97179976808fe6.zip
416. parition equal subset sum
-rw-r--r--partition_equal_subset_sum.c37
-rw-r--r--partition_equal_subset_sum.py25
2 files changed, 42 insertions, 20 deletions
diff --git a/partition_equal_subset_sum.c b/partition_equal_subset_sum.c
index 91156f2..d71deb5 100644
--- a/partition_equal_subset_sum.c
+++ b/partition_equal_subset_sum.c
@@ -7,26 +7,37 @@
* or false otherwise
*/
-bool is_subset_sum(int *nums, int numsSize, int sum) {
- bool dp[numsSize + 1][numsSize + 1];
- for (int i = 0; i <= numsSize; i++)
- dp[i][0] = true;
- for (int i = 1; i <= sum; i++)
- dp[0][i] = false;
- for (int i = 1; i <= numsSize; i++)
- for (int j = 1; j <= sum; j++)
- dp[i][j] = nums[i - 1] <= j ? dp[i - 1][j - nums[i - 1]] || dp[i - 1][j]
- : dp[i - 1][j];
- return dp[numsSize][sum];
+bool memo(int *nums, int **dp, int sum, int idx, int n) {
+ if (!sum)
+ return true;
+ if (idx >= n)
+ return false;
+ if (dp[idx][sum] != -1)
+ return dp[idx][sum];
+ bool pick = false, no_pick = false;
+ if (nums[idx] <= sum)
+ pick = memo(nums, dp, sum - nums[idx], idx + 1, n);
+ no_pick = memo(nums, dp, sum, idx + 1, n);
+ return dp[idx][sum] = (pick || no_pick);
}
bool canPartition(int *nums, int numsSize) {
int sum = 0;
for (int i = 0; i < numsSize; i++)
sum += nums[i];
- if ((sum % 2))
+ if (sum & 1)
return false;
- return is_subset_sum(nums, numsSize, sum / 2);
+ int **dp = (int **)malloc(numsSize * sizeof(int *));
+ for (int i = 0; i < numsSize; i++) {
+ dp[i] = (int *)malloc(((sum >> 1) + 1) * sizeof(int));
+ for (int j = 0; j < ((sum >> 1) + 1); ++j)
+ dp[i][j] = -1;
+ }
+ bool ans = memo(nums, dp, sum >> 1, 0, numsSize);
+ for (int i = 0; i < numsSize; i++)
+ free(dp[i]);
+ free(dp);
+ return ans;
}
int main() {
diff --git a/partition_equal_subset_sum.py b/partition_equal_subset_sum.py
index 7f563b7..3f63a5c 100644
--- a/partition_equal_subset_sum.py
+++ b/partition_equal_subset_sum.py
@@ -13,13 +13,24 @@ class Solution(object):
:type nums: List[int]
:rtype: bool
"""
- total_sum = sum(nums)
- if total_sum & 1:
- return False
- half_sum, dp = total_sum // 2, 1
- for n in nums:
- dp |= dp << n
- return dp & 1 << half_sum
+ n = len(nums)
+ dp = [[-1 for _ in range(((sum(nums) >> 1) + 1))] for _ in range(n)]
+
+ def memo(sm, idx):
+ if sm == 0:
+ return True
+ if idx >= len(nums):
+ return False
+ if dp[idx][sm] != -1:
+ return True if dp[idx][sm] == 1 else False
+ pick, no_pick = False, False
+ if nums[idx] <= sm:
+ pick = memo(sm - nums[idx], idx + 1)
+ no_pick = memo(sm, idx + 1)
+ dp[idx][sm] = 1 if pick or no_pick else 0
+ return True if dp[idx][sm] == 1 else False
+
+ return False if (sum(nums) & 1) else memo(sum(nums) >> 1, 0)
if __name__ == "__main__":