416.分割等和子集

题目

原题 416.分割等和子集

给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

示例 1：

输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。
示例 2：

输入：nums = [1,2,3,5]
输出：false
解释：数组不能分割成两个元素和相等的子集。

分析

本题不能够简单的直接将数组从小到大排序，然后判断左半部分和右半部分的和是否相等，比如对于 [1, 1, 2, 2]，左右两部分的和是 2 和 4，无论如何左半部分也不会和右半部分的和相等，但实际上将它们分为 [1, 2] 和 [1, 2] 就是问题的解。

本题与背包问题（一组带有 weights 的物品，放入一定容量的背包，选取物品的重量之和不能超过背包的总容量）很类似，本题要求选取的数字之和恰好等于某个正整数（数组和的一半）。

模仿背包问题的 DP 解法，创建一个二维布尔数组 dp[i][j]，表示是否在下标范围 0~i 范围内选取一些 numbers 的和正好等于 j。 那么考虑一种边界情况，下标为 i 的 number 是否被选入了 numbers 计算和。

• 当 i 未被选入 numbers 的时候，能推导出以下公式:

dp[i][j] = dp[i-1][j]

• 当 i 被选入了 numbers 的时候，能推导以下公式:

dp[i][j] = dp[i-i][j-nums[i]]

很显然，上述存在另一个边界条件，即 j 和 nums[i] 的大小关系，当 j < nums[i] 的时候，就不能将 nums[i] 加入到 numbers 来得到 j。因此总结下述公式：

dp[i][j] = dp[i-i][j-nums[i]] || dp[i-1][j]  j ≥ nums[i]
dp[i][j] = dp[i-1][j]                        j < nums[i]

public boolean canPartition(int[] nums) {
    int sum = Arrays.stream(nums).sum();
    if(sum%2 != 0) return false;
    int target = sum/2;
    // 初始化 dp 记录状态，表示在 0~i 的范围选择某些数字的和是否能够等于 j
    boolean[][] dp = new boolean[nums.length][target+1];
    // 当 j=0 时，不选择任何的数字就可以，所以初始化为 true
    for(int i=0;i<nums.length;i++){
        dp[i][0]=true;
    }
    // 执行状态转移
    for(int i=1; i<nums.length; i++){
        for(int j=1; j<=target; j++){
            if (j>=nums[i]){
                dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i]];
            } else {
                dp[i][j] = dp[i-1][j];
            }
        }
    }
    return dp[nums.length-1][target];
}