diff options
author | Jack Sangdahl <[email protected]> | 2025-04-06 20:14:42 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-04-06 20:14:42 -0600 |
commit | beff35cecb8082a45325921e6f97179976808fe6 (patch) | |
tree | eba848b0becff05985bce36009728395d2d8c1bc | |
parent | 9b2152674c86116b8a973d7691b239b39f63eb89 (diff) | |
download | leetcode-beff35cecb8082a45325921e6f97179976808fe6.tar.gz leetcode-beff35cecb8082a45325921e6f97179976808fe6.zip |
416. parition equal subset sum
-rw-r--r-- | partition_equal_subset_sum.c | 37 | ||||
-rw-r--r-- | partition_equal_subset_sum.py | 25 |
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__": |