前言
持续更新了
正文
问题来源
本问题来自leetcode上的416题。
问题描述
给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
示例 1:
输入: [1, 5, 11, 5]
输出: true
解释: 数组可以分割成 [1, 5, 5] 和 [11].
示例 2:
输入: [1, 2, 3, 5]
输出: false
解释: 数组不能分割成两个元素和相等的子集.
分析：
func max(a, b int) int {
if a > b {
return a
}
return b
}
func canPartition(nums []int) bool {
if len(nums) < 2 {
return false
}
m := 0
count := 0
for i := 0; i < len(nums); i++ {
count += nums[i]
m = max(m, nums[i])
}
if count % 2 == 1 {
return false
}
target := count/2
if target < m {
return false
}
dp := make([]bool, target+1)
dp[0] = true
for i := 0; i < len(nums); i++ {
for j := target; j >= nums[i]; j-- {
dp[j] = dp[j] || dp[j-nums[i]]
}
}
return dp[target]
}
总结：
勤思考。
结语
不管怎么样好好加油。
