LeetCode-热题100：416. 分割等和子集

题目描述

给你一个 只包含正整数 的 非空 数组 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

代码及注释

func canPartition(nums []int) bool {
    res := 0

    // 计算数组 nums 的总和
    for i := 0; i < len(nums); i++ {
        res += nums[i]
    }
    
    // 如果总和为奇数，不能分割成等和子集，直接返回 false
    if res % 2 == 1 {
        return false
    }
    
    // 将总和除以2，问题转化为是否存在和为 res/2 的子集
    res /= 2
    
    // 初始化一个动态规划数组，dp[i] 表示是否存在和为 i 的子集
    dp := make([]bool, res + 1)
    dp[0] = true

    // 遍历 nums 数组，更新 dp 数组
    for _, num := range nums {
        for j := res; j >= num; j-- {
            dp[j] = dp[j] || dp[j - num]
        }
    }
    
    // 返回 dp[res]
    return dp[res]
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

代码解释

1. 计算数组总和：

   for i := 0; i < len(nums); i++ {
       res += nums[i]
   }
   1
   2
   3

   • 这里通过循环计算数组 nums 的总和。

2. 检查总和是否为奇数：

   if res % 2 == 1 {
       return false
   }
   1
   2
   3

   • 如果数组 nums 的总和 res 是奇数，那么不能将其分割成两个和相等的子集，直接返回 false。

3. 将总和除以2：

   res /= 2
   1

   • 将总和 res 除以 2，问题转化为是否存在和为 res/2 的子集。

4. 动态规划：

   dp := make([]bool, res + 1)
   dp[0] = true
   for _, num := range nums {
       for j := res; j >= num; j-- {
           dp[j] = dp[j] || dp[j - num]
       }
   }
   return dp[res]
   1
   2
   3
   4
   5
   6
   7
   8

   • 初始化一个动态规划数组 dp，其中 dp[i] 表示是否存在和为 i 的子集。
   • 遍历 nums 数组，并更新 dp 数组：
     • dp[j] = dp[j] || dp[j - num] 表示对于每一个数字 num，如果存在和为 j - num 的子集，那么存在和为 j 的子集。

5. 返回结果：

   return dp[res]
   1

   • 返回 dp[res]，判断是否存在和为 res 的子集，即是否可以将数组 nums 分割成两个和相等的子集。

这种方法的时间复杂度是 O(n x target}，其中 n 是数组 nums 的长度，target 是数组 nums 的总和的一半。