求分享 416 的衍生问题的解题思路

[tamer]

https://leetcode-cn.com/problems/partition-equal-subset-sum/

先贴原题:

给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

注意:

每个数组中的元素不会超过 100
数组的大小不会超过 200
示例 1:

输入: [1, 5, 11, 5]

输出: true

解释: 数组可以分割成 [1, 5, 5] 和 [11].

如果现在元素可以弃置,也就是不放入任何一个子集中,求弃置最少元素的分割成 2 个等元素和子集的方案.

如[1,1,3]
即分割成[1][1],3 弃置

目前就想到暴力算法复杂度 3 的 n 次方 ,求个优化思路或者更优方案, 去重 /回溯的剪枝目前也没好的办法

[guchengyehai1]

来个 bfs 的，https://codeshare.io/21mWDj

[guchengyehai1]

不过从 dp 的角度看，有每个元素三种选择，给第一个子集，给第二个子集，扔掉

[guchengyehai1]

https://codeshare.io/2EOYpp 代码没有验证，基本思路应该是这样，再加个 memoization

[geelaw]

提示：令 F(a,b) 为前 a 个元素分成两个和的差的绝对值为 b 的子集最少需要删除元素个数。

时间 n*mn，m 是一个元素的最大值，n 是元素个数。对 a 可用滚动数组技巧优化。

[tamer]

@guchengyehai1 时间复杂度是不是没法优化了,目前 n 接近 20 就算不动了

[tamer]

@guchengyehai1 有没有办法在过程中剪枝, 因为 存在镜像情况, a b 内的元素 对调

[tamer]

@geelaw 老哥, m 是什么的最大值?

之前也想状态压缩, 但没想出证明其正确性的方法.
构成同一差值的 2 个子集的多个方案, 总是选择 删除元素最少的方案, 这样吗

[guchengyehai1]

改了一版，不知道是不是正确的

[guchengyehai1]

验证了一下，memo 优化一下 n 大于 30 都可以跑