LeetCode百题【分割等和子集】

题目描述

给你一个 只包含正整数 的非空数组 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

解法

动态规划
- 将问题转换为：判断是否可以从数组中选出一些数字，使得这些数字的和等于整个数组的元素和的一半
- 特殊判断
  - 元素个数>2
  - 元素和为偶数
  - 数组内不得有单个数>sum/2；
- 定义dp[i][j]为表示从数组的 [0,i] 下标范围内选取若干个正整数（可以是0个），是否存在一种选取方案使得被选取的正整数的和等于 j
- 边界情况
  - 如果不选取任何正整数，则被选取的正整数和等于0。因此对于所有 0≤i<n，都有 dp[i][0]=true
  - 当 i==0 时，只有一个正整数nums[0] 可以被选取，因此 dp[0][nums[0]]=true
- 状态转移方程
  - 当前num>j,不可选，状态由上一个状态转移过来 dp[i][j]=dp[i-1][j];
  - 当前num<=j,可选可不选，二者满足一种即可 dp[i][j]=dp[i-1][j] | dp[i-1][j-num];

class Solution {

    public boolean canPartition(int[] nums) {
        int n=nums.length;
        //1.特殊判断
        if (n<2){
            return false;
        }
        int sum=0;
        int maxNum=Integer.MIN_VALUE;
        for (int num : nums) {
            sum+=num;
            maxNum=Math.max(maxNum, num);
        }
        if (sum%2!=0){
            return false;//和为奇数
        }
        int target=sum/2;//总和的一半

        if (maxNum>target){
            return false;//极端情况
        }

        //2.定义dp->  dp[i][j]为从0-i是否存在若干数和为j,这里j还要考虑0
        boolean[][] dp=new boolean[n][target+1];
        //初始化
        for (int i = 0; i < n; i++) {
            dp[i][0]=true;//都不选 和为0，满足
        }
        dp[0][nums[0]]=true;//定义第一个状态

        //3.动态转移
        for (int i = 1; i < n; i++) {
            int num=nums[i];
            for (int j = 1; j <= target; j++) {
                if (num>j){
                    //不能选
                    dp[i][j]=dp[i-1][j];
                }
                else {
                    //可选可不选
                    dp[i][j]=dp[i-1][j]|dp[i-1][j-num];
                }
            }
        }
        return dp[n-1][target];
    }
}