华为 OD 训练营 · 题解精讲
LC416.分割等和子集
LC416.分割等和子集
题目描述
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
题目解析
解题思路
本题等价于在数组中寻找一个子集，使其和为总和的一半。采用动态规划解决，将问题转化为 0-1 背包问题：每个数字选或不选，能否恰好凑出目标值 target = total // 2。
定义 dp[i][j] 表示从数组前 i+1 个元素（下标 0~i）中能否选出若干元素使其和为 j。状态转移时，对于当前元素 nums[i]，有两种情况：
- 不选：
dp[i][j] = dp[i-1][j] - 选：若
nums[i] <= j，则dp[i][j] = dp[i-1][j - nums[i]]
两者取或运算即可。
关键步骤
1. 计算总和，若为奇数直接返回 False。 2. 初始化 dp[0][nums[0]] = True（前提 nums[0] <= target）。 3. 两层循环遍历 i 从 1 到 n-1，j 从 0 到 target：
- 先继承上一行结果：
dp[i][j] = dp[i-1][j] - 若
nums[i] == j，直接置 True - 若
nums[i] < j，则dp[i][j] |= dp[i-1][j - nums[i]]
4. 返回 dp[n-1][target]。
转移示意图（以 nums=[1,5,11,5], target=11 为例）：
j=0 1 2 3 4 5 6 7 8 9 10 11
i=0 F T F F F F F F F F F F
i=1 F T F F F T T F F F F F
i=2 F T F F F T T F F F F T
i=3 F T F F F T T F F F F T复杂度分析
- 时间复杂度：O(n × target)，其中 n 为数组长度，target 为总和的一半。两层循环嵌套。
- 空间复杂度：O(n × target)，使用二维 dp 数组。可优化为一维，但参考代码未做此优化。
参考代码
class Solution:
def canPartition(self, nums: List[int]) -> bool:
# 使用 total 来保存数组中全部元素的和
total = sum(nums)
# 如果发现 sum 为奇数，那么必然无法拆分为两个相等的整数
if total & 1:
return False
# 获取数组的长度
n = len(nums)
# 获取数组中全部元素之后的一半
# 接下来需要在数组 nums 中寻找一些数字去拼凑为 target
# 如果能找到一些数字之和为 target，那么剩下的数字之和也是 target
target = total // 2
# dp[i][j] 表示 nums 的前 i 个元素能否可以组成和为 j 的结果
# dp[0][0] 表示 nums 的前 0 个元素能否可以组成和为 0 的结果
# dp[2][6] 表示 nums 的前 2 个元素能否可以组成和为 6 的结果
# dp[n - 1][target ] 表示 nums 的前 n - 1 个元素能否可以组成和为 target 的结果
# i 的值从 0 到 n - 1
# j 的值从 0 到 target
dp = [[False] * (target + 1) for _ in range(n)]
# 先初始化 dp[0][nums[0]]
# 如果 nums 的第 0 个元素 nums[0] 小于 target
if nums[0] <= target :
# 那么 nums 的前 0 个元素能否可以组成和为 nums[0] 的结果是 true
# 因为 nums 的前 0 个元素就是 nums[0]
dp[0][nums[0]] = True
# 接下来开始往 dp 数组中填充结果
# i 的值从 1 到 n - 1
for i in range( 1 , n ):
# j 的值从 0 到 target
for j in range( 0 , target + 1 ):
# dp[i][j] 表示 nums 的前 i 个元素能否可以组成和为 j 的结果
# dp[i - 1][j] 表示 nums 的前 i - 1 个元素能否可以组成和为 j 的结果
# 对于 dp[i][j] 来说，如果 dp[i - 1][j] 为 true，那么 dp[i][j] 必然也为 true
# 所以，先初始化 dp[i][j] 的值为 dp[i - 1][j] 的值
# 再通过后面的代码修改 dp[i][j] 中还为 false 的值
dp[i][j] = dp[i - 1][j]
# 如果此时 nums[i] 恰巧为 j
# 那么对于 dp[i][j] 来说，nums 的前 i 个元素可以组成和为 j 的结果
if nums[i] == j :
# 所以 dp[i][j] 为 true
dp[i][j] = True
# 同时继续
continue
# 如果发现 nums[i] 小于 j
if nums[i] < j :
# dp[i][j] 表示 nums 的前 i 个元素能否可以组成和为 j 的结果
# dp[i - 1][j] 表示 nums 的前 i - 1 个元素能否可以组成和为 j 的结果
# dp[i - 1][j - nums[i]] 表示 nums 的前 i - 1 个元素能否可以组成和为 j - nums[i] 的结果
# 那么 dp[i][j] 的结果要为 true
# 1、nums 的前 i - 1 个元素可以组成和为 j
# 2、nums 的前 i - 1 个元素可以组成和为 j - nums[i]
# 对于 1 来说，不用使用 nums[i] 就组成了 j
# 对于 2 来说，前 i - 1 个元素可以组成和为 j - nums[i]，那么加上此时的值 nums[i]，也组成了 j
dp[i][j] = dp[i - 1][j] | dp[i - 1][j - nums[i]]
# dp[n - 1][target ] 表示 nums 的前 n - 1 个元素能否可以组成和为 target 的结果
# 返回这个结果
return dp[n - 1][target]