416. 分割等和子集（动态规划）

416. 分割等和子集

• 题目
• 解题思路
• 代码

题目

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

注意:

• 每个数组中的元素不会超过 100
• 数组的大小不会超过 200

解题思路

这题可以转换为背包问题：要求数组可否被分割成两个元素相同的子集，那不就是要求是否有子集的和是原来和的一半。
即 背包容量为sum的一半，从数组中拿出元素放入背包，能否恰好把背包放满。

1. 这题的状态依旧为两个，因为转化为了背包问题，还是可选择的元素，和背包容量，所以需要一个二维的dp数组

2. dp数组含义：dp[i][j]=x；对于前i个物品。背包容量为j时候，若x=true，则恰好可以把背包装满，x=false，则不能把背包装满

3. base case

   1. dp[0][…]=false：没有物品可以装，当然无法填满背包，在初始化数组的时候就完成了
   2. […][0]=true：当背包容量为0，相当于已经装满了。即已经达到了sum

4. 所以我们要求的结果就是dp[n][sum]，此处的sum为原数组和的一半。所以需要正向遍历。

5. 对于物品只有两种情况，装入或者不装入背包。然后看是否有一种情况能恰好填满背包

代码

class Solution {
      public 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[i][j]=x；对于前i个物品。背包容量为j时候，若x=true，则恰好可以把背包装满，x=false，则不能把背包装满
        boolean[][] dp = new boolean[n + 1][sum + 1];//多的一个大小，是留给base case的

        /*
        base case:
            dp[0][..]=false：没有物品可以装，当然无法填满背包，在初始化数组的时候就完成了
            dp[..][0]=true：当背包容量为0，相当于已经装满了。即已经达到了sum
        */
        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++) {
                /*j-nums[i-1]：背包剩余重量。要注意第i个物品的重量是nums[i-1]，因为i是从1开始的(因为i=0,j=0留给了base case)，而数组的索引是从0开始的。
                 */
                if (j - nums[i - 1] < 0) {
                    // 背包满了无法装入
                    dp[i][j] = dp[i - 1][j];
                } else {
                    //选择装入或者不装入，只要有一个为true，证明存在一种方案恰好装满背包
                    dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]];
                }
            }
        }
        return dp[n][sum];
    }
}