leetcode 416. 分割等和子集

题目描述

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

注意:

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

示例 1:
输入: [1, 5, 11, 5]
输出: true
解释: 数组可以分割成 [1, 5, 5] 和 [11].

示例 2:
输入: [1, 2, 3, 5]
输出: false
解释: 数组不能分割成两个元素和相等的子集.

题解

两个子集相等,可以知道数组的和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
}