题解 | 分割等和子集

题干解析

题设给予我们一个数组，要求我们进行判定所给数组能够拆分为两个总和一致的数组。

算法思路

首先大前提，我们必须知道这个数组所有值的总和，记作sum，当且仅当sum是个偶数时我们才可能将数组拆分为两个等和子集。

同时我们转化问题为，在数组中选择一定数量的元素，使这些元素的总和大小为。于是我们将问题转化为0/1背包问题。设定状态值为dp[i][j]表示使用前i个元素能否填满大小为j的背包。

于是我们有状态转移方程：

设定初始值dp[0][0] = true;开始DP计算即可。

同时由于DP过程状态转移方程只涉及i与i-1，因此可进行滚动优化内存。

实现代码

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = 0;
        for (auto i : nums) sum += i;
        if (sum % 2) return false; // 奇数直接返回不行
        sum >>= 1; // 在此处总和已减半
        vector<bool> dp(sum + 1, false);
        dp[0] = true;
        int min_ = 0;
      	// DP，min_是为了防止越界访问，我们不需要考虑大于sum的背包情况
        for (auto i : nums) {
            min_ = min(min_ + i, sum);
            for (int j = min_; j >= i; --j) {
                dp[j] = dp[j] || dp[j - i];
            }
            if (dp[sum]) return true; // 找到立刻返回，其实也可以最后统一返回dp[sum]
        }
        return false;
    }
};

复杂度分析

• 时间复杂度：
• 空间复杂度：