分割等和子集

Leetcode Link: 416. 分割等和子集 - 力扣（LeetCode）

题目

给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

解法一

思路：从暴力递归到动态规划

• 暴力递归 (超时)，若提前对nums排序就可以了，因为排序了之后base case暗含了剪枝。

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        @cache
        def process(i, tar):
            if tar == 0:
                return True
            
            if i >= len(nums) or tar<0:
                return False
            
            p1 = process(i+1, tar)         # 不要
            p2 = process(i+1, tar-nums[i]) # 要
            return p1 or p2
        
        ssum = sum(nums)
        if ssum % 2 != 0:
            return False
        tar = ssum // 2
        return process(0, tar)

• 动态规划

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        if sum(nums) % 2 != 0: return False
        half = sum(nums) // 2
 
        dp = [[False for _ in range(half+1)] for _ in range(len(nums))]
        # 初始化
        for i in range(len(nums)):
            dp[i][0] = True
        for tar in range(half+1):
            if tar == nums[len(nums)-1]: dp[len(nums)-1][tar] = True
        # 问题退化成用nums里的数字凑half，不再是分子集问题。
        for i in range(len(nums)-2, -1, -1):
            for tar in range(half+1):
                dp[i][tar] = (dp[i+1][tar] or dp[i+1][tar-nums[i]]) if tar-nums[i]>=0 else dp[i+1][tar]
        
        return dp[0][half]