416. Partition Equal Subset Sum - cocoder39/coco39_LC GitHub Wiki

416. Partition Equal Subset Sum

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        list_sum = sum(nums)
        if list_sum % 2 != 0:
            return False
        
        target_sum = list_sum // 2
        
        memo = collections.defaultdict(dict)
        
        def helper(start_idx, target):
            if start_idx == len(nums):
                return target == 0
            
            if target < 0:
                return False
            
            if start_idx in memo and target in memo[start_idx]:
                return memo[start_idx][target]
            
            memo[start_idx][target] = helper(start_idx + 1, target) or helper(start_idx + 1, target - nums[start_idx])
            
            return memo[start_idx][target]
        
        return helper(0, target_sum)