题目描述

给定一个只包含正整数的非空数组，判断数组是否可以分成两个子数组，使得每个子数组的和相等。

注意：
1. 数组里每个元素不超过100.
2. 数组大小不超过200.

样例

输入: [1, 5, 11, 5]
输出: true
解释: 数组可以划分成 [1, 5, 5] 和 [11].

算法1

(动规)

实际上就是求是否存在子数组，使得子数组的和等于整个数组和的1/2。考虑用动规，看成是0-1背包问题的一种变形，dp[i][j]表示考虑前i个数字，是否存在子数组和为j。转移方程为

dp[i][j] = dp[i-1][j] | dp[i-1][j-nums[i]]

（即不选第i个数字或者选第i个数字）

可以用滚动数组进行优化。

时间复杂度

$O(MN)$ M是数组元素和，N是数组元素个数

Python 代码

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

算法2

(哈希)

在动规中由于每次都需要遍历1到target(target = sum(nums) / 2)，当数组元素很大的时候dp的速度就会很慢。有些时候在dp数组里，大部分dp[i][j]都是0，dp数组很稀疏。

dp[i][j]实际上是为了记录考虑前i个数字时，j是否能够通过子数组求和得到，因此可以考虑用sum_set记录能够通过子数组求和得到的数字，每次扩充sum_set（即把原来sum_set里的每个元素都加上nums[i]，类似于dp里选取nums[i]这个元素的过程)，最后判断target是否在sum_set里即可。

时间复杂度

最坏复杂度是$O(MN)$，M是数组元素和，N是数组元素个数，但是平均复杂度会好一些。

Python 代码

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        s = sum(nums) 
        if s % 2 != 0:
            return False
        target = s / 2
        sum_set = set([0]) # 初始的sum_set
        for i in range(0, len(nums)):
            to_add = set() # 加上nums[i]，新增的子数组和
            for ele in sums:
                to_add.add(ele + nums[i])
            sum_set |= to_add # 扩充sum_set
            if target in sums:
                return True
        return False

算法3

(bitset)

（这个做法是参考leetcode里discussion的做法，感觉很巧妙）

在解法2里，比较慢的地方在于选nums[i]时扩充sum_set，需要遍历sum_set里的每个元素，最后还要将加上nums[i]的和并入sum_set里。由于数组里元素都是正整数，可以考虑用bitset来表示子数组和的集合，由于数组元素个数不超过200，每个元素不超过100，因此和的一半不超过10000，可以用10001位的bitset来表示所有可能的子数组的和，bitset[n] = 1表示存在和为n的子数组。

在考虑选nums[i]时，相当于将bitset里所有为1的位置都左移了nums[i]位（即下标加nums[i])，扩充sum_set相当于与原来的bitset取并就行了。

时间复杂度

根据bitset的实现原理，sum_set |= sum_set << nums[i];这一句的复杂度为$O(M/64)$，因此总复杂度为$O(MN/64)$，在leetcode上运行明显比上面两种解法快。

C++ 代码

因为C++里有bitset类，于是就用C++写了.

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        bitset<10001> sum_set;
        sum_set[0] = 1;
        int sum = 0;
        for (int i = 0; i < nums.size(); i ++) {
            sum_set |= sum_set << nums[i];
            sum += nums[i];
        }
        if (sum % 2 == 1)
            return false;
        return sum_set[sum/2];
    }
};