分割等和子集
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
示例 1：
输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。
示例 2：
输入：nums = [1,2,3,5]
输出：false
解释：数组不能分割成两个元素和相等的子集。
题解：
01背包问题，动态规划的思路还是需要多刷题才好练啊，感觉 dp 这里还是差一点
func canPartition(nums []int) bool {
if len(nums) < 2 {
return false
}
sum := 0
for i := 0; i < len(nums); i++ {
sum += nums[i]
}
if sum%2 == 1 {
return false
}
tar := sum / 2
dp := make([]bool, tar+1)
dp[0] = true
for i := 0; i < len(nums); i++ {
for j := tar; j >= nums[i]; j-- {
if dp[j-nums[i]] {
dp[j] = true
}
}
}
return dp[tar]
}
func canPartition(nums []int) bool {
if len(nums) < 2 {
return false
}
sum, maxNum := 0, nums[0]
for i := 0; i < len(nums); i++ {
sum += nums[i]
}
if sum%2 == 1 {
return false
}
tar := sum / 2
if maxNum > tar {
return false
}
dp := make([][]bool, len(nums))
for i := range dp {
dp[i] = make([]bool, tar+1)
}
for i := range dp {
dp[i][0] = true
}
dp[0][nums[0]] = true
for i := 1; i < len(nums); i++ {
for j := 1; j <= tar; j++ {
if j >= nums[i] {
dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i]]
} else {
dp[i][j] = dp[i-1][j]
}
}
}
return dp[len(nums)-1][tar]
}