分割等和子集

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

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

示例 1:
输入: [1, 5, 11, 5]
输出: true
解释: 数组可以分割成 [1, 5, 5] 和 [11].
 

示例 2:
输入: [1, 2, 3, 5]
输出: false
解释: 数组不能分割成两个元素和相等的子集.
 

通过次数96,541提交次数196,065

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/partition-equal-subset-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

动态规划

0-1背包问题变种，解题思路如下：

• 如果所有数字的和是奇数，那么这个数组一定不能分成两个等和的数组
• 如果某个数字大于数组中数字和的1/2，那么数组一定不能分成两个等和的数组
  使用动态规划解决，这是一个0-1背包问题，背包的容量是数字和的1/2，对于某个数字，如果该数字小于背包的剩余容量，那么可以选择是否将该数字加入背包，对应的状态是：

$dp[i][j]=dp[i-1][j]$ 和$dp[i][j]=dp[i-1][j-nums[i]]$如果两种情况满足一种情况，那么$dp[i][j]$就是$true$

对于某个数字如果该数字大于背包的剩余容量，那么就不能选择当前的数字，不可以将当前的数字加入背包

$dp[i][j]=dp[i-1][j]$

class Solution {
    public boolean canPartition(int[] nums) {
        if (nums == null || nums.length == 0) return true;
        int sum = 0;
        int max = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            max = Math.max(max, nums[i]);
        }
        if (max > sum / 2) return false;
        if (sum % 2 != 0) return false;

        int n = nums.length;
        boolean[][] dp = new boolean[n][sum / 2 + 1];

        for (int i = 0; i < nums.length; i++) {
            dp[i][0] = true;
        }

        dp[0][nums[0]] = true;
        // 当当前值小于目标值的剩余值时，可以选择当前的数字也可以不选择当前的数字，选择是dp[i-1][j-nums[i]]，不选择是dp[i-1][j]
        // dp[i - 1][j] | dp[i-1][j - nums[i]];
        // 当当前值大于目标值的剩余值时，不能继续选新的数字了
        // dp[i-1][j]
        for (int i = 1; i < n; i++) {
            int num = nums[i];
            for (int j = 1; j <= sum / 2; j++) {
                if (num < j) {
                    dp[i][j] = dp[i - 1][j] | dp[i - 1][j - num]; // 因为逻辑运算中的或相当于加法运算中的加，所以这里可以通过逻辑运算判断和是否满足条件
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[n - 1][sum / 2];
    }
}

赏

谢谢你请我吃糖果

微信