背包问题变体之子集分割

416. 分割等和子集

题目描述

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

注意:

每个数组中的元素不会超过 100
数组的大小不会超过 200
示例 1:

输入: [1, 5, 11, 5]

输出: true

解释: 数组可以分割成 [1, 5, 5] 和 [11].

示例 2:

输入: [1, 2, 3, 5]

输出: false

解释: 数组不能分割成两个元素和相等的子集.

解题思路

（1）

对于这个问题， 我们可以先对集合求和， 得出 sum ， 把 问题转化为背
包问题：

给一个可装载重量为 sum / 2 的背包和 N 个物品， 每个物品的重量为
nums[i] 。 现在让你装物品， 是否存在一种装法， 能够恰好将背包装满？

（2）

动态规划的套路：

1. 要明确两点， 「状态」 和「选择」 。

   状态有两个， 就是「背包的容量」 和「可选择的物品」 。
   选择就是「装进背包」 或者「不装进背包」 。

2. 要明确 dp 数组的定义

   • dp[i][j] = x 表示， 对于前 i 个物品， 当前背包的容量为 j 时， 若 x
     为 true ， 则说明可以恰好将背包装满， 若 x 为 false ， 则说明不能恰
     好将背包装满。
   • dp[4][9] = true ， 其含义为： 对于容量为 9 的背包， 若只是用前 4 个物品， 可以有一种方法把背包恰好装满。
   • 答案就是 dp[N][sum/2]
   • base case 就是dp[..][0] = true 和 dp[0][..] = false ， 因为背包没有空间的时候， 就相当于装满了， 当没有物品可选择的时候， 肯定没办法装满背包。

3. 根据「选择」 ， 思考状态转移的逻辑

   dp[i - 1][j-nums[i-1]] 也很好理解： 你如果装了第 i 个物品， 就要看背包的剩余重量 j - nums[i-1] 限制下是否能够被恰好装满。

   • 不把这第 i 个物品装进背包

     那么是否能够恰好装满背包， 取决于上一个状态 dp[i-1][j] ， 继承之前的结果

   • 把这第 i 个物品装进了背包

     那么是否能够恰好装满背包， 取决于状态 dp[i - 1][j-nums[i-1]]

j - nums[i-1] 的重量可以被恰好装满， 那么只要把第 i个物品装进去， 也可恰好装满 j 的重量； 否则的话， 重量 j 肯定是装不满的。

---

完整代码求解为：

二维数组

public static boolean canPartition(int[] nums){
        int sum = 0;
        for (int num : nums)
            sum += num;
        //和为奇数，则不可能分成两个和相等的集合
        if (sum % 2 != 0){
            return false;
        }
        int n = nums.length;
        sum = sum / 2;
        //构建dp数组
        boolean[][] dp = new boolean[n + 1][sum + 1];
        //base case
        for (int i = 0; i <= n; i++) {
            dp[i][0] = true;
        }
        //开始状态转移
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= sum; j++) {
                if (j - nums[i - 1] < 0){
                    //背包容量不足，肯定不能装入第i个物品
                    dp[i][j] = dp[i - 1][j];
                }else {
                    //装入或装入背包
                    //看着是否存在一种情况能够切好装满
                    dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]];
                }
            }
        }

        return dp[n][sum];
    }

一维数组

    public static boolean canPartition_1(int[] nums) {
        int sum = 0,n = nums.length;
        for (int num : nums) {
            sum += num;
        }
        if (sum % 2 != 0)
            return false;
        sum = sum / 2;
        boolean[] dp = new boolean[sum + 1];
        //base case
        dp[0] = true;
        for (int i = 0; i < n; i++) {
            for (int j = sum; j >= 0; j--) {
                if (j - nums[i] >= 0){
                    dp[j] = dp[j] || dp[j - nums[i]];
                }
            }
        }
        return dp[sum];

    }

只在一行dp 数组上操作， i 每进行一轮迭代， dp[j] 其实就相当于 dp[i-1][j] ， 所以只需要一维数组就够用了。

参考：labuladong