Leetcode 416.分割等和子集

题目描述：

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

示例 1：

1
2
3

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

示例 2：

1
2
3

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

提示：

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

链接：

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

题目分析

  一开始想到的是类似于贪心这样的做法，比如维护两个数组，每次总是先添加到较小的那个数组，或者是从大到小贪心地加入数字直到它们的和等于总和的一半。但是考虑了一下总是能举出反例，导致找出答案的复杂度肯定不太美丽。无奈瞄了一眼官方题解，好家伙，原来是 NP 完全问题。（我在观察到题目的数据数量级的时候就意识到这可能没有复杂度很低的做法，毕竟数量级挺小）然后才了解到，这道题目是经典的 0-1 背包问题，有空需要了解一下相关方面的题目了。
  经典的 0-1 背包问题也是使用动态规划来做的，主要思想就是，对于每一个元素考虑要不要放入背包（也就是分类讨论，这也符合动态规划的特点）。这道题目，我们可以视为我们要从这个数组中找出若干个数，让它们的和达到数组总和的一半，而这个数目就是背包的大小 target，而我们对元素一个一个进行考虑。这样我们令 dp[i][j] 表示 0 ~ i 个元素能否取出若干个数凑成大小 j。那么第 i 个数有放入或者不放入两种做法。

• 放入。那么如果 0 ~ i-1 能凑出 j-nums[i]，我们就可以达成。
• 不放入。那么如果 0 ~ i-1 能凑出 j，我们也可以达成。

  注意一下不要越界（也即 j >= nums[i] 才能放入），那么便有这样的状态转移：

  边界条件是什么呢？当 j == 0 时，所有数都不放入即可，我们可以视为 true。而元素一个一个考虑，假设有 n 个元素，最后的结果就是 dp[n-1][target]。
  观察到，动态状态中每一层（也即外层 i）只与上一层的状态有关，那么我们可以进行降维，类似于滚动数组的思想，只使用一层来存储状态。实际上这也是 0-1 背包问题的常见优化方向。需要注意的是，这个时候内层循环需要从大到小遍历。为什么呢？相关的上一层状态是更小的状态，那么从大到小遍历才可以保证进行转移的状态是上一层的状态而不是这一层的状态。这样我们便完成了空间降维。
  这道题还可以先进行一部分的剪枝，比如数组元素个数小于 2 个，那是不可能划分成两个数组的。比如数组的总和是奇数，这样肯定无法分成两个和为其一半的数组。比如数组中的最大元素已经超过和的一半了，这样其他元素和也不够一半，同样无法分割。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        if(nums.size() < 2) return false;
        int sum = 0, maxNum = 0;
        for(const int& num : nums){
            sum += num;
            maxNum = max(maxNum, num);
        }
        if((sum & 1) == 1) return false;
        int target = sum / 2;
        if(maxNum > target) return false;

        vector<bool> dp(target+1, false);
        dp[0] = true;
        for(int i = 0; i < nums.size(); i++){
            for(int j = target; j >= nums[i]; j--){
                if(dp[j - nums[i]]){
                    dp[j] = true;
                }
            }
        }
        return dp[target];
    }
};

  时间复杂度：$O(n\times target)$，其中 $n、target$ 分别表示数组的大小和数组总和的一半。也就是我们双层遍历的时间复杂度。
  空间复杂度：$O(target)$，其中 $target$ 是数组总和的一半。也就是我们经过优化后用来存储状态的数组。