题解 | #分割等和子集#

题意整理

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

方法一（动态规划）

1.解题思路

可以转化为0-1背包问题。只要从数组中找出若干个数，使得这些数的和等于所有数之和的一半即可。假设数组所有数的累加和为sum，则背包的容量为sum/2。在转换之前，可以提前过滤掉一些不合法的情况。当sum为奇数时，显然不能分成相等的两半，直接返回false，当数组最大值大于sum/2时，显然也不能分成相等的两半，直接返回false。

状态定义： $d p [i] [j]$ 表示i个元素内，是否能凑成目标和为j。
状态初始化：0个元素时凑成0的情况设为true。
状态转移：遍历所有可能的容量，如果大于等于当前元素，要么选，要么不选，即 $d p [i + 1] [j] = d p [i] [j] ∣ d p [i] [j - n u m s [i]]$ 。如果小于当前元素，直接默认不选，即 $d p [i + 1] [j] = d p [i] [j]$ 。

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @return bool布尔型
     */
    
    
    public boolean partition (int[] nums) {
        //sum记录累加和，max记录最大值
        int sum=0;
        int max=0;
        //遍历nums数组
        for(int num:nums){
            sum+=num;
            max=Math.max(max,num);
        }
        //如果累加和为奇数，直接返回false，如果最大值大于累加和的一半，也直接返回false
        if(sum%2==1) return false;
        if(max>sum/2) return false;
        int n=nums.length;
        //定义dp数组，dp[i][j]表示i个元素内，是否能凑成目标和为j
        boolean[][] dp=new boolean[n+1][sum/2+1];
        
        //初始化
        dp[0][0]=true;
        for(int i=0;i<n;i++){
            for(int j=0;j<=sum/2;j++){
                //如果大于当前元素，要么选，要么不选
                if(j>=nums[i]){
                    dp[i+1][j]=dp[i][j]|dp[i][j-nums[i]];
                }
                //否则，默认不选
                else{
                    dp[i+1][j]=dp[i][j];
                }
                
            }
        }
        return dp[n][sum/2];
    }
    
}

3.复杂度分析

时间复杂度：总共两层循环，最多执行 $n * (s u m / 2 + 1)$ 次，所以时间复杂度是 $O (n * s u m)$ 。
空间复杂度：需要额外大小为 $(n + 1) * (s u m / 2 + 1)$ 的dp数组，所以空间复杂度为 $O (n * s u m)$ 。

方法二（空间优化）

1.解题思路

由于每次状态转移只与上一行的情况有关，所以dp数组只需要容量这一层维度即可。另外转移的过程中，每个数只能选一次，所以需要从后往前遍历容量。

图解展示： alt

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @return bool布尔型
     */
    
    
    public boolean partition (int[] nums) {
        //分别记录累加和以及最大值
        int sum=0,max=0;
        //遍历nums数组
        for(int num:nums){
            sum+=num;
            max=Math.max(max,num);
        }
        //如果累加和为奇数，直接返回false，如果最大值大于累加和的一半，也直接返回false
        if(sum%2==1) return false;
        if(max>sum/2) return false;
        //定义dp数组,dp[i]表示数组中的数字能否凑成目标和为i的情况
        boolean[] dp=new boolean[sum/2+1];
        int n=nums.length;
        //初始化
        dp[0]=true;
        for(int i=0;i<n;i++){
            //每个数只能选一次，所以从后往前更新
            for(int j=sum/2;j>=nums[i];j--){
                dp[j]|=dp[j-nums[i]];
            }
        }
        return dp[sum/2];
    }
    

}

3.复杂度分析

时间复杂度：总共两层循环，最多执行 $n * (s u m / 2 + 1)$ 次，所以时间复杂度是 $O (n * s u m)$ 。
空间复杂度：需要额外大小为 $s u m / 2 + 1$ 的dp数组，所以空间复杂度为 $O (s u m)$ 。