LeetCode 416. 分割等和子集

Categories:

Tags:

题目描述
思路分析
参考代码

题目描述

🔥 416. 分割等和子集

思路分析

我们首先计算整个数组的元素和 sum，并且检查是否为奇数。如果 sum 为奇数，那么不可能将其分割成两个和相等的子集，因此直接返回 false。

将目标和 target 设为 sum 的一半，因为如果可以找到一个子集的元素和为 target，那么另一个子集的元素和也会为 target。

我们创建了一个一维数组 dp，其中 dp[i] 表示是否可以找到一个子集的元素和为 i。初始时，我们将 dp[0] 设置为 true，因为可以选择不取任何元素来得到和为 0 的子集。

遍历数组 nums 中的每个元素 num，然后从 target 向 num 遍历，更新 dp 数组。具体的更新规则为 dp[j] = dp[j] || dp[j-num]，表示如果可以找到一个子集的元素和为 j - num，那么就可以找到一个子集的元素和为 j。这是典型的 01 背包问题思路。

最终，返回 dp[target]，表示是否可以找到一个子集的元素和为 target，即是否可以将原始数组分割成两个和相等的子集。

参考代码

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 题解

write your code here

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/63371951