416. 分割等和子集（Medium）

题目描述

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

样例

Input: nums = [1,5,11,5]
Output: true
# 分为[1, 5, 5] 和 [11] 两个子集

题解

若是要等分为两份的话，总和必须是偶数。而且存在几个数字之和等于 sum(nums)/ 2。

因为每个数字只能使用一次，所以就转换为 0-1 背包问题

代码

func sum(nums []int) int {
    ans := 0
    for _, num := range nums {
        ans += num
    }
    return ans 
}

func canPartition(nums []int) bool {
   target := sum(nums)

   if target % 2 == 1 { // 奇数一定分不开
       return false 
   }
   target = target / 2
   
   n := len(nums)

   // 新建 dp[n + 1][target + 1] 的数组
   dp := make([][]bool, n + 1)
   for i := 0; i <= n; i ++ {
       dp[i] = make([]bool, target + 1)
   }

   // base case 
   for i := 0; i < n + 1; i++ {
       dp[i][0] = true
   }
  
   for cap := 1; cap <= target; cap++ {
       for i := 1; i <= n; i++ {
           // 注意点：
           // !!! 这里是 减 nums[i - 1] 因为 0 把 整体向右移，i 对应的就是 nums[i - 1] 
           if cap - nums[i - 1] >= 0 && 
              dp[i - 1][cap - nums[i - 1]] { // 当容量够，可以更新的时候
               dp[i][cap] = true
           } else { // 不能更新的话，起码我可以不加入第 i 个元素，背包的大小是不变的
               dp[i][cap] = dp[i][cap] || dp[i - 1][cap] 
           }
       } 
   }
   
   return dp[n][target]
}