416. 分割等和子集问题（动态规划）

题目

题解

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        # badcase
        if not nums:
            return True
        # 不能被2整除
        if sum(nums) % 2 != 0:
            return False

        # 状态定义：dp[i][j]表示当背包容量为j，用前i个物品是否正好可以将背包填满，True/False
        dp = [[False for j in range(sum(nums)+1)] for i in range(len(nums)+1)]
        for i in range(len(nums) + 1):
            dp[i][0] = True
        
        # 状态转移
        for i in range(1, len(nums) + 1):
            for j in range(1, sum(nums) + 1):
                if j - nums[i-1] >= 0:
                    # 选择用第i个物品或者不用
                    dp[i][j] = dp[i - 1][j - nums[i-1]] or dp[i-1][j]
                else:
                    dp[i][j] = dp[i-1][j]
        return dp[len(nums)][int(sum(nums) / 2)]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23