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

【题目描述】

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

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

【示例】

【代码】​​wulafly​​

01背包	01 背包，即数组中的元素不可重复使用， 外循环遍历 arrs，内循环遍历 target，且内循环倒序:
完全背包	场景1：数组中的元素可重复使用并且不考虑元素之间顺序 arrs 放外循环（保证 arrs 按顺序）target内循环（正序）
	场景2：如果组合问题需考虑元素之间的顺序，需 target 放在外循环，将 arrs 放在内循环（正序）

// 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
    }
}