分割等和子集动态规划

1. 题目描述

给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
注意:

每个数组中的元素不会超过100
数组的大小不会超过200

示例 1:

输入: [1, 5, 11, 5]

输出: true

解释: 数组可以分割成 [1, 5, 5] 和 [11].

示例 2:

输入: [1, 2, 3, 5]

输出: false

解释: 数组不能分割成两个元素和相等的子集.

2. 题解

public boolean canPartition(int[] nums) {
	int n = nums.length;
	if (n < 2) {
		return false;
	}
	int sum = 0, maxNum = 0;
	for (int num : nums) {
		sum += num;
		maxNum = Math.max(maxNum, num);
	}
	if (sum % 2 != 0) {
		return false;
	}
	int target = sum / 2;
	if (maxNum > target) {
		return false;
	}
	boolean[][] dp = new boolean[n][target + 1];
	for (int i = 0; i < n; i++) {
		dp[i][0] = true;
	}
	dp[0][nums[0]] = true;
	for (int i = 1; i < n; i++) {
		int num = nums[i];
		for (int j = 1; j <= target; j++) {
			if (j >= num) {
				dp[i][j] = dp[i - 1][j] | dp[i - 1][j - num];
			} else {
				dp[i][j] = dp[i - 1][j];
			}
		}
	}
	return dp[n - 1][target];
}

这里要将数组划分为两个子集，数组至少要有两个元素。
如果数组中所有元素的和sum是奇数，不可能划分出元素和相等的两个子集；如果sum是偶数，则令target=sum/2，需要判断是否可以从数组中选出一些数字，使得这些数字的和等于target。
如果数组中最大的元素maxNum大于target，则除了maxNum以外的所有元素之和一定小于target，因此也不可能划分出元素和相等的两个子集。

创建二维数组dp，包含n行target+1列，其中dp[i][j]表示从数组的[0,i]下标范围内选取若干个正整数（可以是0个），是否存在一种选取方案使得被选取的正整数的和等于j。

当i = 0时，选取nums[0]使得j等于1。
当i = 1时，有三种情况：

选取nums[0]使得j等于1；
选取nums[1]使得j等于5；
同时选取nums[0]和nums[1]使得j等于6。

注意到当i = 1时，要使得j等于1，由于nums[1]大于1，所以不选取nums[1]。
因此，dp[1][1] = dp[0][1]，即不选取nums[1]的情况下，是否存在使得j等于1的选取方案。

当i = 1时，要使得j等于5，由于nums[1]小于等于5。因此，dp[1][5] = dp[0][5] | dp[0][0]，这里的dp[0][5]表示不选取nums[1]，是否存在使得j等于5的选取方案，dp[0][0]表示选取nums[1]，是否存在一种选取方案使得被选取的正整数的和等于0。

当i = 1时，要使得j等于6，由于nums[1]小于等于6。因此，dp[1][6] = dp[0][6] | dp[0][1]，这里的dp[0][1]表示选取nums[1]，再看看i = 0的选取方案，显然当i = 0时，选取nums[0]使得j等于1。

最后，dp[3][11]表示从数组的[0,3]下标范围内选取若干个正整数，是否存在一种选取方案使得被选取的正整数的和等于11。

另一种方法：
遍历数组nums，遍历的每个元素都选取。比如，遍历nums[0]时选取nums[0]，遍历nums[1]时选取nums[1]。
当遍历nums[0]时，要使得j等于1，dp[1] |= dp[0]。
当遍历nums[1]时，要使得j等于6，dp[6] |= dp[1]；要使得j等于5，dp[5] |= dp[0]。
注意到dp[6] |= dp[1]，它表示选取nums[1]，是否存在一种选取方案使得被选取的正整数的和等于1。

public boolean canPartition(int[] nums) {
	int n = nums.length;
	if (n < 2) {
		return false;
	}
	int sum = 0, maxNum = 0;
	for (int num : nums) {
		sum += num;
		maxNum = Math.max(maxNum, num);
	}
	if (sum % 2 != 0) {
		return false;
	}
	int target = sum / 2;
	if (maxNum > target) {
		return false;
	}
	boolean[] dp = new boolean[target + 1];
	dp[0] = true;
	for (int i = 0; i < n; i++) {
		int num = nums[i];
		for (int j = target; j >= num; --j) {
			dp[j] |= dp[j - num];
		}
	}
	return dp[target];
}

参考：

分割等和子集 - 分割等和子集 - 力扣（LeetCode）