题目

思路

使用0-1背包的思路。 之前0-1背包是说有N个物品，一个最大承重重量为W的背包。每个物品都有各自的重量和value,要让放入背包中物品价值总和最大。

这道题如何对应成0-1背包，看下面的分析。

背包的大小：要想两个子集元素和相等，我们计算nums数组的sum。如果sum是奇数的话，直接返回false。如果是偶数的话，我们的目标就是求 sum/2的子集。我们设为 sum/2。

物品的重量和价值：物品的重量在这道题里为元素的数值。价值也设为元素的数值，因为我们想让dp[i]为物品的重量。

dp数组的含义：这里用二维dp数组。dp[i] [j]表示从[0,i]的元素里面选，在j的背包容量下的最大重量。

当dp[i] [sum/2] = sum/2的时候，我们就返回true。

再次理解最大重量：在sum/2这个背包容量下，实际背的重量小于等于sum/2。为了能让其取到最大重量所以我们需要 dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-nums[i]]+nums[i]);

其他都和0-1背包代码一样。建议看了0-1背包后再来看这道题。

代码

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public boolean canPartition(int[] nums) {
        int len = nums.length;
        int sum = 0;
        for (int num : nums)
            sum += num;
        if (sum % 2 != 0)
            return false;
        int target = sum / 2;

        int[][] dp = new int[len][target + 1];

        //初始化
        for (int j = nums[0]; j <= target; j++) {
            dp[0][j] = nums[0];
        }

        for (int i = 1; i < len; i++) {
            for (int j = 1; j <= target; j++) {
                if (j < nums[i]) { 
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-nums[i]]+nums[i]);
                }
            }
        }
        return dp[len - 1][target] == target;
    }
}
//leetcode submit region end(Prohibit modification and deletion)