0416. 分割等和子集

0416. 分割等和子集 #

  • 标签:数组、动态规划
  • 难度:中等

题目大意 #

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

解题思路 #

如果两个子集和相等,则两个子集元素和刚好等于整个数组元素和的一半。这就相当于 0-1 背包问题。

定义 dp[i][j] 表示从 [0, i] 个数中任意选取一些数,放进容量为 j 的背包中,价值总和最大为多少。则 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - nums[i]] + nums[i])

转换为一维 dp 就是:dp[j] = max(dp[j], dp[j - nums[i]] + nums[i])

然后进行递推求解。最后判断 dp[target]target 是否相等即可。

代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        size = 100010
        dp = [0 for _ in range(size)]
        sum_nums = sum(nums)
        if sum_nums & 1:
            return False
        target = sum_nums // 2
        for i in range(len(nums)):
            for j in range(target, nums[i]-1, -1):
                dp[j] = max(dp[j], dp[j - nums[i]] + nums[i])

        if dp[target] == target:
            return True
        return False
本站总访问量  次  |  您是本站第  位访问者