分割等和子集
难度:
标签:
题目描述
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
示例 1：
输入：nums = [1,5,11,5] 输出：true 解释：数组可以分割成 [1, 5, 5] 和 [11] 。
示例 2：
输入：nums = [1,2,3,5] 输出：false 解释：数组不能分割成两个元素和相等的子集。
提示：
1 <= nums.length <= 2001 <= nums[i] <= 100
代码结果
运行时间: 30 ms, 内存: 16.0 MB
// Java Stream Solution
// 思路：
// 1. 使用Stream计算总和。
// 2. 如果总和是奇数，则返回false。
// 3. 以动态编程的方式计算是否可以分成和相等的两个子集。
import java.util.Arrays;
import java.util.stream.IntStream;
public class StreamSolution {
public boolean canPartition(int[] nums) {
int sum = IntStream.of(nums).sum();
if (sum % 2 != 0) return false;
int target = sum / 2;
boolean[] dp = new boolean[target + 1];
dp[0] = true;
Arrays.stream(nums).forEach(num -> {
for (int j = target; j >= num; j--) {
dp[j] = dp[j] || dp[j - num];
}
});
return dp[target];
}
}解释
方法:
这个题解使用了动态规划的思路。首先判断数组的总和是否为奇数，如果是则不可能平分成两个等和子集。然后将目标和设为总和的一半。接下来使用一个整数dp作为状态，其二进制表示中从右往左第i位表示是否存在一个和为i的子集。通过遍历数组中的每个数x，将dp中所有已经置为1的位向右移动x位，再与原dp取或，这样就在dp中记录了当前数组前缀中所有可能的子集和。如果右移后dp的最低位变为1，说明存在一个子集的和等于目标和，直接返回True。遍历结束后，如果dp最低位仍为0，说明不存在符合条件的子集划分，返回False。
时间复杂度:
O(n * target)
空间复杂度:
O(1)
代码细节讲解
🦆
在题解中，为什么总和为奇数时就可以直接判断无法平分成两个等和子集？
▷🦆
请问在进行动态规划时，为什么使用位运算而不是传统的动态规划表来记录子集和的存在性？
▷🦆
题解中提到的`dp |= dp >> x`操作具体是如何更新dp的状态的？请解释这一步中位运算的逻辑。
▷🦆
为什么题解中判断`if dp & 1`能够确定是否存在一个子集的和等于目标和？
▷