416. 分割等和子集

🟠   🔖  数组 动态规划  🔗 力扣 LeetCode

题目

Given an integer array nums, return true if you can partition the array into two subsets such that the sum of the elements in both subsets is equal orfalse otherwise.

Example 1:

Input: nums = [1,5,11,5]

Output: true

Explanation: The array can be partitioned as [1, 5, 5] and [11].

Example 2:

Input: nums = [1,2,3,5]

Output: false

Explanation: The array cannot be partitioned into equal sum subsets.

Constraints:

• 1 <= nums.length <= 200
• 1 <= nums[i] <= 100

题目大意

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

解题思路

思路一：动态规划

这是一个典型的动态规划问题，可以通过状态转移方程来解决。问题可以转化为背包问题，即是否存在一组元素，使得它们的和恰好为数组元素和的一半。

定义一个二维数组 dp，其中 dp[i][j] 表示在前 i 个元素中是否存在一组元素的和等于 j。状态转移方程如下：

dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]]

• dp[i-1][j] 表示不选取第 i 个元素。
• dp[i-1][j-nums[i-1]] 表示选取第 i 个元素。

初始化状态：dp[i][0] = true，即对于前 i 个元素，总是可以找到一组元素的和为 0（即不选取任何元素）。

最终结果为 dp[n][target]，其中 n 为数组长度，target 为数组元素和的一半。

复杂度分析

• 时间复杂度：O(n * target)，其中 n 是数组长度，target 是数组元素和的一半。
• 空间复杂度：O(n * target)，使用了一个二维动态规划数组。

---

思路二：压缩状态的动态规划

注意到 dp[i][j] 都是通过上一行 dp[i-1][..] 转移过来的，再之前所有行的数据都不会再使用了。所以，我们可以对动态规划进行状态压缩，将二维 dp 数组压缩为一维，节约空间复杂度：

• dp[j] 表示是否可以使用当前元素得到和为 j 的子集。
• 遍历 nums 数组中的每个数字 num，并更新 dp 数组。需要注意的是 j 应该从后往前反向遍历，确保了我们在更新当前状态时所依赖的状态已经被正确计算。
• 对于每个 j 从 target 到 num，根据 dp[j] 和 dp[j - num] 的值来更新 dp[j]。
• 最终结果存储在 dp[target] 中。如果为 true，表示存在一个和为 target 的子集，即数组可以被分割成两个和相等的子集。

代码

动态规划

/**
 * @param {number[]} nums
 * @return {boolean}
 */
function canPartition(nums) {
	const n = nums.length;
	const sum = nums.reduce((acc, num) => acc + num, 0);

	// 如果数组元素和为奇数，不可能分割成两个和相等的子集
	if (sum % 2 !== 0) {
		return false;
	}

	const target = sum / 2;
	const dp = new Array(n + 1)
		.fill(false)
		.map(() => new Array(target + 1).fill(false));

	// 初始化状态
	for (let i = 0; i <= n; i++) {
		dp[i][0] = true;
	}

	// 动态规划计算
	for (let i = 1; i <= n; i++) {
		for (let j = 1; j <= target; j++) {
			if (j < nums[i - 1]) {
				// 背包容量不足，不能装入第 i 个物品
				dp[i][j] = dp[i - 1][j];
			} else {
				// 装入或不装入背包
				dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]];
			}
		}
	}

	return dp[n][target];
}

压缩状态的动态规划

/**
 * @param {number[]} nums
 * @return {boolean}
 */
function canPartition(nums) {
	const n = nums.length;
	const sum = nums.reduce((acc, num) => acc + num, 0);

	// 如果数组元素和为奇数，不可能分割成两个和相等的子集
	if (sum % 2 !== 0) {
		return false;
	}

	const target = sum / 2;
	const dp = new Array(target + 1).fill(false);

	// 初始状态：空子集的和为 0
	dp[0] = true;

	// 动态规划计算
	for (let num of nums) {
		for (let j = target; j >= num; j--) {
			dp[j] = dp[j] || dp[j - num];
		}
	}

	return dp[target];
}

相关题目

题号	标题	题解	标签	难度
698	划分为k个相等的子集		位运算 记忆化搜索 数组 3+
1981	最小化目标值与所选元素的差		数组 动态规划 矩阵
2025	分割数组的最多方案数		数组 哈希表 计数 2+
2035	将数组分成两个数组并最小化数组和的差		位运算 数组 双指针 4+
2395	和相等的子数组		数组 哈希表
2518	好分区的数目		数组 动态规划
2578	最小和分割		贪心 数学 排序