aboutsummaryrefslogtreecommitdiff
path: root/partition_equal_subset_sum.py
diff options
context:
space:
mode:
Diffstat (limited to 'partition_equal_subset_sum.py')
-rw-r--r--partition_equal_subset_sum.py25
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__":