// 0/1 背包; dp[i]: 是否存在子集和为i
// 时间 O(n * target), 空间O(target)
func canPartition(nums []int) bool {
sum := 0
n := len(nums)
for i := 0; i < n; i++ {
sum += nums[i]
}
if sum % 2 == 1 {
return false
}
target := sum / 2
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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21