题解 | #分割等和子集#

题目的主要信息：

• 给定一个只包含正整数的数组，从中取出若干个数，使取出的数之和与剩余数字之和相等

方法一：递归及优化

具体做法：

我们可以求得数组的累加和sum，即只要从数组中选出一个子集的元素，元素之和为sum的一半，那剩余的元素之和就是另一半，则题目就变成了从数组中选择若干个数使其和为目标值。

我们可以考虑递归选择，每次对于当前元素，可以选择加入子集或是不加入，相应修改距离目标值剩余的值，进入子问题（即后续数组中寻找和为目标剩余值），直到数组结尾或是找到或找不到。

很遗憾，这种方法超时了。

class Solution {
public:
    bool recur(vector<int>& nums, int begin, int rest){
        if(rest == 0) //剩余数字为0，找到
            return true;
        if(rest < 0 || begin == nums.size())  //剩余数字小于0或者达到数组结尾，找不到
            return false;
        //对于当前元素，选择加入子集与不加入
        if(recur(nums, begin + 1, rest) || recur(nums, begin + 1, rest - nums[begin]))
            return true;
        return false;
    }
    bool partition(vector<int>& nums) {
        int sum = 0;
        if(nums.size() <= 1) //空数组或者长度为1的数组不可分
            return false;
        for(int i = 0; i < nums.size(); i++) //求数组累加和
            sum += nums[i];
        if(sum % 2 == 1) //累加和为奇数也不可分
            return false;
        return recur(nums, 0, sum / 2); //递归求解，找出数组中部分子集和为累加和一半
    }
};

复杂度分析：

• 时间复杂度：$O(2^n)O(2^n)$，二叉树型递归
• 空间复杂度：$O(n)O(n)$，递归栈的最大深度

改进：

每次递归会重复计算很多子问题，因此我们可以用一个数组记录哪些子问题被计算过了，数组中用unordered_set表示选出的集合，后续递归中优先检查数组，如果这个子问题就被计算过了录入了数组，就不用继续计算了。

class Solution {
public:
    vector<unordered_set<int>> dp;
    bool recur(vector<int>& nums, int begin, int rest){
        if(rest == 0) //剩余数字为0，找到
            return true;
        if(rest < 0 || begin == nums.size() || dp[begin].find(rest) != dp[begin].end())  //剩余数字小于0或者达到数组结尾,或者当前开头的值已经记录了
            return false;
        dp[begin].insert(rest);
        //对于当前元素，选择加入子集与不加入
        if(recur(nums, begin + 1, rest) || recur(nums, begin + 1, rest - nums[begin]))
            return true;
        return false;
    }
    bool partition(vector<int>& nums) {
        int sum = 0;
        dp.resize(nums.size());
        if(nums.size() <= 1) //空数组或者长度为1的数组不可分
            return false;
        for(int i = 0; i < nums.size(); i++) //求数组累加和
            sum += nums[i];
        if(sum % 2 == 1) //累加和为奇数也不可分
            return false;
        return recur(nums, 0, sum / 2); //递归求解，找出数组中部分子集和为累加和一半
    }
};

复杂度分析：

• 时间复杂度：$O(n\ast sum)O(n*sum)$，递归的过程中最多只会把数组填满，其中数组中的set填满是$O(sum)O(sum)$级别的
• 空间复杂度：$O(n\ast sum)O(n*sum)$，用于记录重复计算的数组空间

方法二：动态规划

具体做法：

依旧是求从数组中取出若干个数，看能不能达到累加和为目标值，其中目标值为数组累加和的一半。

创建二维bool型数组dp，包含$nn$，$sum\mathrm{/}2+1sum/2+1$列，其中$dp[i][j]dp[i][j]$表示从数组的$[0,i][0,i]$下标范围内选取若干个正整数，是否存在一种选取方案使得被选取的正整数的和等于$jj$。初始时，dp中的全部元素都是false。

边界状态如下：

• 如果不选取任何正整数，则被选取的正整数等于0。因此对于所有 ，都有 $\mathit{\text{dp}}[i][0]=\text{true}\backslash textit\{dp\}[i][0]=\backslash text\{true\}$。
• 当 $i==0i==0$ 时，只有一个正整数 $\mathit{\text{nums}}[0]\backslash textit\{nums\}[0]$可以被选取，因此 $\mathit{\text{dp}}[0][\mathit{\text{nums}}[0]]=\text{true}\backslash textit\{dp\}[0][\backslash textit\{nums\}[0]]=\backslash text\{true\}$。

后续遍历所有的数组长度，对于当前元素nums[i]和从1开始的每一个目标值，如果目标值大于等于当前元素，那我们可以选或者不选，选了目标值要相应缩小，当然如果目标值小于当前元素，那只能不选，由此可以填满dp数组。转移方程如下：

class Solution {
public:
    bool partition(vector<int>& nums) {
        int sum = 0;
        if(nums.size() <= 1) //空数组或者长度为1的数组不可分
            return false;
        for(int i = 0; i < nums.size(); i++) //求数组累加和
            sum += nums[i];
        if(sum % 2 == 1) //累加和为奇数也不可分
            return false;
        //dp[i][j]表示从数组的[0,i]下标范围内选取若干个正整数，是否存在一种选取方案使得被选取的正整数的和等于j
        vector<vector<bool> > dp(nums.size() + 1, vector<bool>(sum / 2 + 1, false));
        //初始化边界
        for(int i = 0; i < nums.size(); i++)
            dp[i][0] = true;
        dp[0][nums[0]] = true;
        for(int i = 1; i < nums.size(); i++){ //遍历数组长度
            int num = nums[i]; //得到当前的值
            for(int j = 1; j <= sum / 2; j++){ //对于全部目标值
                if(j >= num) //可以选或者不选
                    dp[i][j] = dp[i - 1][j] | dp[i - 1][j - num];
                else //目标值不够，不能选
                    dp[i][j] = dp[i - 1][j];
            }
        }
        return dp[nums.size() - 1][sum / 2];
    }
};

复杂度分析：

• 时间复杂度：$O(n\ast sum)O(n*sum)$，其中sum为整个数组的累加和，两层循环
• 空间复杂度：$O(n\ast sum)O(n*sum)$，辅助数组dp的空间