0416：分割等和子集（★）

2016-02-20 约 409 字预计阅读 1 分钟次阅读

力扣第 416 题

题目

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

示例 1：

输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。

示例 2：

输入：nums = [1,2,3,5]
输出：false
解释：数组不能分割成两个元素和相等的子集。

提示：

1 <= nums.length <= 200
1 <= nums[i] <= 100

分析

#1

令 s 为数组的和，问题相当于找子集满足和等于 s/2
这可以看作背包问题，递推即可

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        s = sum(nums)
        if s%2:
            return False
        s //= 2
        f = [1]+[0]*s
        for x in nums:
            for i in range(s,x-1,-1):
                f[i] |= f[i-x]
        return bool(f[-1])

785 ms

#2

由于递推时只关心 f 值为 1 的元素，所以可以直接用 set 维护

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        s = sum(nums)
        if s%2:
            return False
        s //= 2
        vis = set()
        for x in nums:
            vis |= {y+x for y in vis|{0} if y+x<=s}
        return s in vis

534 ms

#2

由于 vis 集合的递推只涉及到加法，所以可以用二进制优化
用二进制状态 st 表示 vis 集合，集合内所有数加上 x 即是 st « x

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        s = sum(nums)
        if s%2:
            return False
        s //= 2
        st = 0
        for x in nums:
            st |= (st|1)<<x
        return bool(st&1<<s)

37 ms

目录

0416：分割等和子集（★）

题目

分析

#1

#2

#2

解答