LeetCode 416. 分割等和子集

题目描述

✅ 416. 分割等和子集

image-20250528223343286

思路分析

这道题本质上是一个 背包问题，即能否从 nums 中选出一些元素，使得这些元素的和等于 sum(nums)/2。

我们可以使用动态规划来解决这个问题，定义 dp[i] 表示是否能够从数组中选出一些元素，使得它们的和等于 i。

image-20250528222857053

参考代码



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23



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[0] = true

	for _, num := range nums {
		for i := target; i >= num; i-- {
			dp[i] = dp[i] || dp[i-num]
		}
	}

	return dp[target]
}

➡️ 点击查看 Java 题解



1



write your code here
本文作者:
本文链接: https://hgnulb.github.io/blog/2025/63371951
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！