diff options
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__": |