题解 | #分割等和子集#

题目的主要信息：

给定一个只包含正整数的数组 nums ，请问能否把这个数组取出若干个数使得取出的数之和和剩下的数之和相同。

方法一：递归（超时）

首先计算数组nums的元素之和sum，如果找得到等和子集，等和子集的和为sum/2，所以如果sum为奇数，则不可能找到等和子集。当sum为偶数时，用dfs函数进行递归处理，每次都对当前元素进行选或不选操作，直到找到和为sum/2的子集。 alt 具体做法：

class Solution {
public:
    bool dfs(vector<int>& nums, int iter, int sum){
        if(sum == 0) {//剩余和为sum=0时，结束递归
            return true;
        }
        if(sum < 0 || iter == nums.size())//剩余sum小于0或者达到数组结尾,或者当前值已经记录
            return false;
        //对于nums[iter]，选择加入子集,sum变为sum-nums[iter]或不加入
        if(dfs(nums, iter + 1, sum) || dfs(nums, iter + 1, sum - nums[iter])){
            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 ){ //如果和为奇数，不可能找到和为sum/2的子集
            return false;
        }else {
            return dfs(nums, 0, sum / 2); //递归找出数组中和sum/2的子集
        }
    }
};

复杂度分析：

时间复杂度： $O (2^{n})$ ，递归函数是二叉树结构。
空间复杂度： $O (n)$ ，递归栈大小为n。

方法二：

动态规划。首先计算数组nums的元素之和sum，如果找得到等和子集，等和子集的和为sum/2，所以如果sum为奇数，则不可能找到等和子集。当sum为偶数时，用动态规划，dp[i][j]表示i个元素内，是否取出若干个数使得和为j，用两个for循环更新动态数组，如果dp[i][j]为true，第i个元素可选可不选，如果选择的话，dp[i+1][j+nums[i]]为true；如果不选择的话，dp[i+1][j]为true。最后返回dp[n][sum/2]。

具体做法：

class Solution {
public:
bool partition(vector<int>& nums) {
        int sum=0;
        //遍历nums数组，计算和
        for(int i=0;i<nums.size();i++){
            sum+=nums[i];
        }
        //sum为奇数则无法找到等和子集
        if(sum%2==1){
            return false;
        }
        int n=nums.size();
        //动态数组dp，dp[i][j]表示i个元素内，是否取出若干个数使得和为j
        bool dp[n+1][sum+1];
        //初始化动态数组
        dp[0][0]=true;
        for(int i=0;i<n;i++){//更新动态数组
            for(int j=0;j<=sum;j++){
                if(dp[i][j]){
                    dp[i+1][j+nums[i]]=true;//选择元素nums[i]
                    dp[i+1][j]=true;//不选择元素nums[i]
                }
            }
        }
        return dp[n][sum/2];
}
};

复杂度分析：

时间复杂度： $O (n * s u m)$ ，两个for循环的复杂度为 $O (n * s u m)$ 。
空间复杂度： $O (n * s u m)$ ，dp数组大小为 $O (n * s u m)$ 。