这是一个创建于 2035 天前的主题，其中的信息可能已经有所发展或是发生改变。
https://leetcode-cn.com/problems/partition-equal-subset-sum/
先贴原题:
给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
注意:
每个数组中的元素不会超过 100
数组的大小不会超过 200
示例 1:
输入: [1, 5, 11, 5]
输出: true
解释: 数组可以分割成 [1, 5, 5] 和 [11].
如[1,1,3]
即分割成[1][1],3 弃置
目前就想到暴力算法复杂度 3 的 n 次方 ,求个优化思路或者更优方案, 去重 /回溯的剪枝目前也没好的办法
第 1 条附言 · 2020 年 11 月 16 日
 |
2 guchengyehai1 2020 年 11 月 16 日 via Android不过从 dp 的角度看，有每个元素三种选择，给第一个子集，给第二个子集，扔掉 |
 |
4 geelaw 2020 年 11 月 16 日 via iPhone提示：令 F(a,b) 为前 a 个元素分成两个和的差的绝对值为 b 的子集最少需要删除元素个数。 时间 n*mn，m 是一个元素的最大值，n 是元素个数。对 a 可用滚动数组技巧优化。 |
 |
7 tamer 2020 年 11 月 16 日@geelaw 老哥, m 是什么的最大值? 之前也想状态压缩, 但没想出证明其正确性的方法. |
|
9 guchengyehai1 2020 年 11 月 16 日 via Android验证了一下，memo 优化一下 n 大于 30 都可以跑 |
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。