【题解 | 01背包】分割等和子集

分割等和子集

力扣：416. 分割等和子集

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

示例 1：

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

示例 2：

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

提示：

• 1 <= nums.length <= 200
• 1 <= nums[i] <= 100

解题

这道题可以用01背包来求解。

我们需要判断是否可以将数组分割成两个子集，使得两个子集的元素和相等。这等价于从数组中选取一些数字，使得这些数字的和等于整个数组的和的一半，并且每个数字只能选一次，这就转化为了一个01背包问题，其中背包的容量是整个数组的和的一半，每个物品的重量和价值都是数组中的一个数字。

具体求解时，我们创建一个一维数组dp，其中dp[j]表示背包容量为j时能装的最大价值。对于数组中的每一个数字num，我们都有两个选择：装入背包或者不装入背包。

• 如果我们装入背包，那么dp[j]就等于dp[j-num]+num
• 如果我们不装入背包，那么dp[j]就保持不变。

我们选择这两者的较大值作为新的dp[j]。

最后，我们只需要判断dp[target]是否等于target，如果等于，那么说明存在一种方案可以使得两个子集的元素和相等，否则不存在。

class Solution {
    public boolean canPartition(int[] nums) {
        int n = nums.length;
        if(nums == null || n == 0) return false;
        int sum = 0;
        for(int num : nums) {
            sum += num;
        }
        if((sum & 1) == 1) return false;  // 奇数肯定没有答案
        int target = sum / 2;
        int[] dp = new int[target + 1];
        for(int num : nums) {
            for(int j = target; j >= num; j--) {
                // 第 i 个物品（数字）的重量是 num，其价值也是 num
                dp[j] = Math.max(dp[j], dp[j-num] + num);
            }
        }
        return dp[target] == target;
    }
}

dp[target]表示的是我们能够通过选择数组中的一些数字，得到的和最接近target（数组总和的一半）的值。如果dp[target]等于target，那么说明我们可以通过选择数组中的一些数字，正好得到和为target的子集。