代码随想录算法训练营|day42

416.分割等和子集

该问题转换为在数组中找到元素和target=sum(nums)/2即可，为0/1背包问题，dp[i]表示是否存在子集和为i。
初始化：dp[0]=true，表示和为0，不需要选取任何元素，为真
如果和为奇数或者数组中最大值大于target无法分成两个等和子集

func canPartition(nums []int) bool {
	sum, maxNum := 0, 0
	for _, num := range nums {
		maxNum = max(maxNum, num)
		sum += num
	}
	if sum%2 != 0 {
		return false
	}
	target := sum / 2
	if maxNum > target {
		return false
	}
	dp := make([]bool, target + 1)
	dp[0] = true
	for _, num := range nums {
		for i := target; i >= num; i-- {
			dp[i] = dp[i] || dp[i - num]
		}
	}
	return dp[target]
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

代码随想录文章详解

01背包理论基础
01背包理论基础（滚动数组）
416.分割等和子集