essay
hot100-分割等和子集
#算法
hot100——分割等和子集
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
示例 1：
输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。
示例 2：
输入：nums = [1,2,3,5]
输出：false
解释：数组不能分割成两个元素和相等的子集。
提示：
1 <= nums.length <= 200
1 <= nums[i] <= 100
解法
// canPartition 判断是否可以将数组分割成两个和相等的子集
func canPartition(nums []int) bool {
// 计算总和
sum := 0
for _, num := range nums {
sum += num
}
// 如果总和为奇数，不可能平分
if sum%2 != 0 {
return false
}
target := sum / 2 // 需要凑出的目标值
dp := make([]bool, target+1) // dp[i] 表示能否选出一些数使它们的和为 i
dp[0] = true // 不选任何数时和为0
// 遍历每个数
for _, num := range nums {
// 从后往前更新 dp，避免同一个数被重复使用
for j := target; j >= num; j-- {
if dp[j-num] {
dp[j] = true
}
}
}
return dp[target]
}