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 /partition_equal_subset_sum.py | |
parent | 9b2152674c86116b8a973d7691b239b39f63eb89 (diff) | |
download | leetcode-beff35cecb8082a45325921e6f97179976808fe6.tar.gz leetcode-beff35cecb8082a45325921e6f97179976808fe6.zip |
416. parition equal subset sum
Diffstat (limited to 'partition_equal_subset_sum.py')
-rw-r--r-- | partition_equal_subset_sum.py | 25 |
1 files changed, 18 insertions, 7 deletions
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__": |