【LeeCode】416. 分割等和子集 -- todo

【题目描述】

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

​​​​https://leetcode.cn/problems/partition-equal-subset-sum/​​​

【示例】

【代码】​​wulafly​​

// 2023-1-5

import java.util.Arrays;

class Solution {
    public boolean canPartition(int[] nums) {
        int sum = Arrays.stream(nums).sum();
        // 隐藏的背包: 2个子集的元素和相等, target必然是sum的一半
        int target = sum / 2;
        // 如果sum不是偶数,则必然不可能分为2个相等的子集
        if (sum % 2 != 0) return false;
        // dp[i] 表示是否存在和为 i 的 num 组合
        boolean[] dp = new boolean[target + 1];
        dp[0] = true;
        // 01背包问题：元素不可重复，外层物品，内层背包且倒序
        for(int num: nums){
            for (int i = target; i >= num ; i--) {
                // dp[i]的值以来其本身或者dp[i-num]
                dp[i] = dp[i] || dp[i - num];
            }
        }
        return dp[target];
    }
}
public class Test {
    public static void main(String[] args) {
        new Solution().canPartition(new int[]{1,5,11,5});  // 输出: true, 数组可以分割成 [1, 5, 5] 和 [11]
        new Solution().canPartition(new int[]{1,2,3,5});   // 输出: false
    }
}