LeetCode热题100--416. 分割等和子集--中等

题目

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

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

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

题解

importjava.math.BigInteger;classSolution{publicbooleancanPartition(int[]nums){ints=0;for(intx:nums){s+=x;}if(s%2!=0){returnfalse;}s/=2;BigIntegerf=BigInteger.ONE;for(intx:nums){f=f.or(f.shiftLeft(x));// f |= f << x;}returnf.testBit(s);// 判断 f 中第 s 位是否为 1}}

解析

出自：三种写法：记忆化搜索 / 递推 / bitset 优化（Python/Java/C++/C/Go/JS/Rust）

importjava.math.BigInteger;classSolution{publicbooleancanPartition(int[]nums){// 计算数组所有元素的总和 sints=0;for(intx:nums){s+=x;}// 如果总和是奇数，则无法分成两个相等的子集（因为和必须是整数）if(s%2!=0){returnfalse;}// 目标子集和为总和的一半s/=2;// 使用 BigInteger 模拟位集（bitmask），f 的第 i 位为 1 表示“可以组成和为 i”// 初始状态：f = 1（二进制 ...0001），表示和为 0 总是可以达成（空子集）BigIntegerf=BigInteger.ONE;// 遍历每个数字 xfor(intx:nums){// 核心操作：f = f OR (f << x)// 含义：对于当前所有可达的和 i（f 的第 i 位为 1），// 新增一个选择：加上 x，得到和 i + x// 所以将 f 左移 x 位（表示所有和都加 x），再与原 f 合并（OR）f=f.or(f.shiftLeft(x));// 等价于 f |= f << x（但 BigInteger 无 |= 运算符）}// 检查第 s 位是否为 1：如果是，说明可以组成和为 s 的子集// 即存在一个子集，其元素和等于总和的一半 → 可分割returnf.testBit(s);// testBit(n) 返回第 n 位是否为 1（从最低位 0 开始计数）}}