416. 分割等和子集
题目描述
输入一个非空数组 nums，其中每个数都是正整数。
把数组中的每个元素都分到两组之一，判断能否让两组元素之和相同。
可以做到就返回 true，否则返回 false。
示例 1
输入：nums = [1,5,11,5] 输出：true
解释：可分为 [1,5,5] 和 [11]，两组和都是 11。
示例 2
输入：nums = [1,2,3,5] 输出：false
解释：总和为 11，是奇数，无法平分。
数据范围
1 <= nums.length <= 2001 <= nums[i] <= 100
解题思路：0-1 背包（一维 DP）
总和为奇数直接失败；目标为总和一半，用 0/1 背包判断能否恰好选出目标。
为什么正确
dp[s] 表示只使用已经处理的数时能否凑出 s，倒序更新保证每个数只用一次。
复杂度分析
时间 O(n×sum)，空间 O(sum)。
易错点
内层必须从 target 向下遍历，否则同一个数字可能在一次处理中被重复使用。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
from typing import List
class Solution:
def canPartition(self, nums: List[int]) -> bool:
total = sum(nums)
if total % 2:
return False
target = total // 2
dp = [False] * (target + 1)
dp[0] = True
for num in nums:
for s in range(target, num - 1, -1):
dp[s] = dp[s] or dp[s - num]
return dp[target]class Solution {
public boolean canPartition(int[] nums) {
int total = Arrays.stream(nums).sum();
if (total % 2 == 1)
return false;
int target = total / 2;
boolean[] dp = new boolean[target + 1];
dp[0] = true;
for (int num : nums)
for (int s = target; s >= num; s--)
dp[s] = dp[s] || dp[s - num];
return dp[target];
}
}class Solution {
public:
bool canPartition(vector<int>& nums) {
int total = accumulate(nums.begin(), nums.end(), 0);
if (total % 2)
return false;
int target = total / 2;
vector<bool> dp(target + 1, false);
dp[0] = true;
for (int num : nums)
for (int s = target; s >= num; s--)
dp[s] = dp[s] || dp[s - num];
return dp[target];
}
};func canPartition(nums []int) bool {
total := 0
for _, num := range nums {
total += num
}
if total%2 == 1 {
return false
}
target := total / 2
dp := make([]bool, target+1)
dp[0] = true
for _, num := range nums {
for s := target; s >= num; s-- {
dp[s] = dp[s] || dp[s-num]
}
}
return dp[target]
}var canPartition = function(nums) {
const total = nums.reduce((a, b) => a + b, 0);
if (total % 2)
return false;
const target = total / 2;
const dp = Array(target + 1).fill(false);
dp[0] = true;
for (const num of nums)
for (let s = target; s >= num; s--)
dp[s] = dp[s] || dp[s - num];
return dp[target];
};function canPartition(nums: number[]): boolean {
const total = nums.reduce((a, b) => a + b, 0);
if (total % 2)
return false;
const target = total / 2;
const dp: boolean[] = Array(target + 1).fill(false);
dp[0] = true;
for (const num of nums)
for (let s = target; s >= num; s--)
dp[s] = dp[s] || dp[s - num];
return dp[target];
};其他解法
一维 DP 逐个状态更新，直观易懂；位集合把同一批状态打包成机器字并行转移，速度快但依赖位运算技巧。
解法 2：位集合子集和 时间 O(n·sum/w)，空间 O(sum/w)
用一个大整数（位集合）的第 s 位表示“能否凑出和 s”。初始只有第 0 位为 1。每读入一个数 num，执行 bits |= bits << num，表示在所有已能凑出的和上再加 num。最后检查第 sum/2 位。
本质仍是子集和 DP，但一次位运算同时更新 w 位（w 为机器字长），常数小很多。依赖语言的位集合或大整数支持，不便输出具体方案。
class Solution:
def canPartition(self, nums: List[int]) -> bool:
total = sum(nums)
if total % 2:
return False
target = total // 2
mask = (1 << (target + 1)) - 1
bits = 1
for x in nums:
bits = (bits | (bits << x)) & mask
return (bits >> target) & 1 == 1class Solution {
public boolean canPartition(int[] nums) {
int total = 0;
for (int x : nums) total += x;
if (total % 2 != 0) return false;
int target = total / 2;
BigInteger mask = BigInteger.ONE.shiftLeft(target + 1).subtract(BigInteger.ONE);
BigInteger bits = BigInteger.ONE;
for (int x : nums) bits = bits.or(bits.shiftLeft(x)).and(mask);
return bits.testBit(target);
}
}class Solution {
public:
bool canPartition(vector<int>& nums) {
int total = 0;
for (int x : nums) total += x;
if (total % 2) return false;
int target = total / 2;
bitset<10001> bits;
bits[0] = 1;
for (int x : nums) bits |= bits << x;
return bits[target];
}
};func canPartition(nums []int) bool {
total := 0
for _, x := range nums {
total += x
}
if total%2 != 0 {
return false
}
target := total / 2
// 用 []uint64 手写位集合：第 s 位为 1 表示能凑出和 s
words := target/64 + 1
set := make([]uint64, words)
set[0] = 1
for _, x := range nums {
ws, bs := x/64, uint(x%64)
// set |= set << x，从高位往低位更新，避免覆盖还没读取的字
for i := words - 1; i >= ws; i-- {
v := set[i-ws] << bs
if bs > 0 && i-ws-1 >= 0 {
v |= set[i-ws-1] >> (64 - bs)
}
set[i] |= v
}
}
return set[target/64]>>uint(target%64)&1 == 1
}var canPartition = function(nums) {
let total = 0;
for (const x of nums) total += x;
if (total % 2) return false;
const target = total / 2;
const mask = (BigInt(1) << BigInt(target + 1)) - BigInt(1);
let bits = BigInt(1);
for (const x of nums) bits = (bits | (bits << BigInt(x))) & mask;
return ((bits >> BigInt(target)) & BigInt(1)) === BigInt(1);
};function canPartition(nums: number[]): boolean {
let total = 0;
for (const x of nums) total += x;
if (total % 2) return false;
const target = total / 2;
const mask = (BigInt(1) << BigInt(target + 1)) - BigInt(1);
let bits = BigInt(1);
for (const x of nums) bits = (bits | (bits << BigInt(x))) & mask;
return ((bits >> BigInt(target)) & BigInt(1)) === BigInt(1);
}