416. 分割等和子集 #

leetcode 链接： https://leetcode-cn.com/problems/partition-equal-subset-sum/

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

注意：

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

示例 1:

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

输出：true

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

示例 2:

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

输出：false

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

方法一：0-1 背包问题

// 0-1 背包问题
// dp[i][target] 表示 nums[0, i] 区间内是否能找到和为 target 的组合
// 对于每个 nums[i]，如果 nums[i] <= target，可以选择 or 不选，但只要有一个为 true，dp[i][target]=true
//      dp[i][target] = dp[i-1][target] || dp[i][target-nums[i]]
// 如果 nums[i] > target，只能不选，故：
//      dp[i][target] = dp[i-1][target]
func canPartition(nums []int) bool {
	n := len(nums)
	if n < 2 {
		return false
	}
	
	sum := 0
	maxNum := 0
	for _, num := range nums {
		sum += num
		if num > maxNum {
			maxNum = num
		}
	}
	// 和为奇数
	if sum%2 != 0 {
		return false
	}
	
	// 最大值超过和的一半
	target := sum / 2
	if maxNum > target {
		return false
	}
	
	var dp = make([][]bool, n)
	for i := range dp {
		dp[i] = make([]bool, target+1)
		// nums 数组均为正数，如果不选取任何 nums[i]，则被选取的正整数的和等于 0
		dp[i][0] = true
	}
	// 只有一个元素 nums[0] 可取时，构成初始值 dp[0][nums[0]] 为 true
	dp[0][nums[0]] = true
	for i := 1; i < n; i++ {
		for j := 1; j <= target; j++ {
			if nums[i] <= j {
				dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i]]
			} else {
				dp[i][j] = dp[i-1][j]
			}
			// 剪枝
			if dp[i][target] {
				return true
			}
		}
	}
	return dp[n-1][target]
}

方法 2：动态规划降维

func canPartition(nums []int) bool {
	n := len(nums)
	if n < 2 {
		return false
	}
	
	sum := 0
	maxNum := 0
	for _, num := range nums {
		sum += num
		if num > maxNum {
			maxNum = num
		}
	}
	// 和为奇数
	if sum%2 != 0 {
		return false
	}
	
	// 最大值超过和的一半
	target := sum / 2
	if maxNum > target {
		return false
	}
	
	var dp = make([]bool, target+1)
	dp[0] = true
	dp[nums[0]] = true
	for i := 1; i < len(nums); i++ {
		// 采用逆序，如果采用正序 dp[j-nums[i]] 会被之前的操作更新为新值
		// dp[j](new) = dp[j](old) || dp[j - nums[i]](old)
		for j := target; j >= nums[i]; j-- {
			if dp[target] {
				return true
			}
			dp[j] = dp[j] || dp[j-nums[i]]
		}
	}
	return dp[target]
}