LeetCode 416. 分割等和子集

题目描述

🔥 416. 分割等和子集

思路分析

  1. 我们首先计算整个数组的元素和 sum，并且检查是否为奇数。如果 sum 为奇数，那么不可能将其分割成两个和相等的子集，因此直接返回 false。
  2. 将目标和 target 设为 sum 的一半，因为如果可以找到一个子集的元素和为 target，那么另一个子集的元素和也会为 target。
  3. 我们创建了一个一维数组 dp，其中 dp[i] 表示是否可以找到一个子集的元素和为 i。初始时，我们将 dp[0] 设置为 true，因为可以选择不取任何元素来得到和为 0 的子集。
  4. 遍历数组 nums 中的每个元素 num，然后从 target 向 num 遍历，更新 dp 数组。具体的更新规则为 dp[j] = dp[j] || dp[j-num]，表示如果可以找到一个子集的元素和为 j - num，那么就可以找到一个子集的元素和为 j。这是典型的 01 背包问题思路。
  5. 最终，返回 dp[target]，表示是否可以找到一个子集的元素和为 target，即是否可以将原始数组分割成两个和相等的子集。

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

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
	for _, num := range nums {
		for j := target; j >= num; j-- {
			dp[j] = dp[j] || dp[j-num]
		}
	}
	return dp[target]
}

🍏 点击查看 Java 题解

1

write your code here

相似题目

题目 难度 题解
划分为 k 个相等的子集 Medium  
本文作者:
本文链接: https://hgnulb.github.io/blog/63371951
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！