416. Partition Equal Subset Sum

class Solution:
    def canPartition(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        # 0/1 背包问题——看看是否能选择某些数填满 sum(nums) // 2
        if not nums:
            return False
        summ = sum(nums)
        if summ % 2 != 0:
            return False
        c = summ // 2
        
        # 记忆化搜索
        memo = []
        for _ in range(len(nums)):
            memo.append([-1] * (c + 1))
        
        # return self.__try_partition(nums, len(nums) - 1, c, memo)
        
        # 动态规划
        memo = [nums[0] == i for i in range(c + 1)]
        for i in range(1, len(nums)):
            for j in range(c, nums[i] - 1, -1):
                memo[j] = memo[j] or memo[j - nums[i]]
        return memo[c]

    def __try_partition(self, nums, idx, c, memo):
        # [0 ... idx] 是否能填满 c
        # if c == 0:
        #     return True
        # if idx < 0 or c < 0:
        #     return False
        # return self.__try_partition(nums, idx - 1, c) or self.__try_partition(nums, idx - 1, c - nums[idx])
        
        if c == 0:
            return True
        if idx < 0 or c < 0:
            return False
        if memo[idx][c] != -1:
            return memo[idx][c] == 1
        memo[idx][c] = 1 if (self.__try_partition(nums, idx - 1, c, memo) or self.__try_partition(nums, idx - 1, c - nums[idx], memo)) else 0
        return memo[idx][c] == 1