未分類
5 11 月 2020

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

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

資深大佬 : tamer 2

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 次方 ,求个优化思路或者更优方案, 去重 /回溯的剪枝目前也没好的办法

大佬有話說 (9)

  • 資深大佬 : 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 都可以跑