leetcode 416. 分割等和子集

题解

两个子集相等,可以知道数组的和sum肯定为偶数,然后问题就变为,判断数组中是否存在和为sum/2的子集,使用背包问题的动态规划,计算出pack可以存储的数值和

示例代码(go)

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