欢迎24级新生

2242. Partition Equal Subset Sum (Medium)

给定一个正整数数组,求是否可以把这个数组分成和相等的两部分。

输入

输入是一个一维正整数数组

输出

输出时一个布尔值

样例

标准输入 复制文本
 [1,5,11,5]
标准输出 复制文本
true

提示

本题等价于 0-1 背包问题,设所有数字和为 sum,我们的目标是选取一部分物品,使得它们的总和为 sum/2。这道题不需要考虑价值,因此我们只需要通过一个布尔值矩阵来表示状态转移矩阵。注意边界条件的处理

登录以提交代码。
单点时限 1 秒
内存限制 128 MB
提交 0
通过 0