416.M 分割等和子集

Problem: 416. 分割等和子集

[TOC]

思路

动态规划。

令dp[i]表示是否存在一个子数组使得和为i，则该题其实就是要找到一个子数组，使和为整个数组总和的一半。

由于都是正整数，所以数组元素个数为1，则不可能找到分割方式。如果数组的总和为奇数，也不可能找到分割方式。

对于第i个元素而言，对于任意的总和j，当j大于等于nums[i]时，可以采取两种策略，选择（dp[j]）或者不选择(dp[j-nums[i]])。

Code

func canPartition(nums []int) bool {
	if len(nums) < 2 {
		return false
	}

	sum := 0
	for _, num := range nums {
		sum += num
	}

	if sum%2 != 0 {
		return false
	}

	target := sum / 2
	dp := make([]bool, target+1)
	dp[0] = true
	for i := 1; i < len(nums); i++ {
		for j := target; j >= nums[i]; j-- {
			dp[j] = dp[j] || dp[j-nums[i]]
		}
	}

	return dp[target]
}