题目描述

解题思路

满足以下四个条件：

• 背包的体积为sum / 2
• 背包要放入的商品（集合里的元素）重量为 元素的数值，价值也为元素的数值
• 背包如果正好装满，说明找到了总和为 sum / 2 的子集。
• 背包中每一个元素是不可重复放入。

即可套入0-1背包。
由于每个数字只能放一次，可以使用0-1背包！！！
本题怎么将0-1背包运用上呢？
背包即是总和的一半。
物品即是每个数组的数字。
重量即是每个数组的数字的值。

• 确定dp数组以及下标的含义

01背包中，dp[j] 表示： 容量为j的背包，所背的物品价值可以最大为dp[j]。
套到本题，dp[j]表示 背包总容量是j，最大可以凑成j的子集总和为dp[j]。

• 确定递推公式

01背包的递推公式为：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
本题，相当于背包里放入数值，那么物品i的重量是nums[i]，其价值也是nums[i]。
所以递推公式：dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);

• dp数组如何初始化

在01背包，一维dp如何初始化，已经讲过，
从dp[j]的定义来看，首先dp[0]一定是0。
如果如果题目给的价值都是正整数那么非0下标都初始化为0就可以了，如果题目给的价值有负数，那么非0下标就要初始化为负无穷。

• 确定遍历顺序

滚动数组注意遍历背包得倒序。

• 举例推导dp数组

dp[j]的数值一定是小于等于j的。
如果dp[j] == j 说明，集合中的子集总和正好可以凑成总和j，理解这一点很重要。
最后如果背包的容量等于了可以凑成的总和，那么返回true。

public boolean canPartition(int[] nums) {
    int sum = 0;
    for (int i = 0; i < nums.length; i++) {
        sum += nums[i];
    }
    if (sum % 2 == 1) return false; // 如果没有总和为 sum/2 的子集
    int target = sum / 2;   // 背包的最大重量
    int dp[] = new int[10001];  // 根据题目计算出最大的背包容量
    // 使用以为数组来模拟背包问题
    for (int i = 0; i < nums.length; i++) { // 遍历nums，i相当于物品重量是nums[i]，价值也是nums[i]
        for (int j = target; j >= nums[i]; j--) {   // 倒叙遍历背包的最大容量
            dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
        }
    }
    // 集合中的元素正好可以凑成总和target
    if (dp[target] == target) return true;
    return false;
}