当前位置：首页 > backend >正文

【leetcode100】分割等和子集

backend 2025/5/20 7:39:40

1、题目描述

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

示例 1：

输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。

示例 2：

输入：nums = [1,2,3,5]
输出：false
解释：数组不能分割成两个元素和相等的子集。

2、初始思路

2.1 先验知识：0-1背包问题

2.1.1 0-1背包的描述：

有n件物品和⼀个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装⼊背包里物品价值总和最⼤。

使用动态规划的思路：

（1）确定dp数组及其含义

对于0-1背包问题，dp[i][j]/dp[i]表示背包能装下 j kg物品时，其最大价值。(dp[i][j]表示使用二维数组进行表示，dp[i]表示使用一维数组进行表示）

（2）递推公式

经过观察，递推公式应表示为：

dp[i][j] = max(dp[i-1][j], value[i] + dp[i-1][j-weight[i]])
dp[j] = max(dp[j], value[i] + dp[j-weight[i]])

也就是，遍历物品，在物品能装进背包的情况下，考虑是否将其装进背包，其价值计算为当前物品的质量+背包减去当前物品重量所能装的最大价值。

（3）初始化dp数组

初始化数组，可将其价值均初始化0

m = len(weight)
dp = [[0] * (bagweight+1) for _ in range(m)]
dp = [0] * (bagweight+1)

（4）遍历顺序

当使用二维数组时，由于每个值都可以保存，因此可以从前向后进行遍历；

而当使用一维数组时，只能倒叙进行遍历，这样可以避免物品重复选择。此外，当使用一维数组时，只能先遍历物品，再遍历背包，因为要倒叙遍历，先遍历背包的话每个背包中将只能装一个物品。

2.1.2 代码

示例为：

（1)二维数组

class Solution:def bag(self, bagweight, weight, value):m = len(weight)dp = [[0] * (bagweight+1) for _ in range(m)]for i in range(m):for j in range(1, bagweight+1):if weight[i] > bagweight:dp[i][j] = dp[i-1][j]else:dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]] + value[i])return dp[m-1][bagweight]
solution = Solution()
bagweight = 4
weight = [1,3,4]
value = [15,20,30]
res = solution.bag(bagweight, weight, value)
print(res)

（2）一维数组

class Solution:def bag2(self, bagweight, weight, value):m = len(weight)dp = [0]*(bagweight+1)for i in range(m):for j in range(bagweight, weight[i]-1, -1):dp[j] = max(dp[j], dp[j-weight[i]]+value[i])return dp[bagweight]
solution = Solution()
bagweight = 4
weight = [1,3,4]
value = [15,20,30]
res = solution.bag2(bagweight, weight, value)
print(res)

2.2 思路

本题可以套用0-1背包的思路，也就是，将nums中的每个数的质量和价值都认为是其本身，背包容量为数组和的一半，这样，如果能找到dp[target] == target，那么表示nums可以被分为两个和相等的子集。

2.3 代码

class Solution:def canPartition(self, nums: List[int]) -> bool:target = sum(nums) // 2n = len(nums)if sum(nums) % 2 != 0:return Falsedp = [0] * (target+1)for i in range(n):for j in range(target, nums[i] - 1, -1):dp[j] = max(dp[j], nums[i] + dp[j - nums[i]])return dp[target] == target

3 优化算法

3.1 思路

本题主要的问题为能否找到子集，因此使用True/False 更自然且更高效。

3.2 代码

class Solution:def canPartition(self, nums: List[int]) -> bool:target = sum(nums) // 2n = len(nums)if sum(nums) % 2 != 0:return Falsedp = [False] * (target+1)dp[0] = Truefor i in range(n):for j in range(target, nums[i] - 1, -1):dp[j] = dp[j] or dp[j-nums[i]]return dp[target]