LeetCode416：分割等和子集

要求

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

---

思路

做一个等价转换：是否可以从输入数组中挑选出一些正整数，使得这些数的和 等于 整个数组元素的和的一半。数组的和一定得是偶数。

方法：动态规划

状态定义：dp[i][j]表示从数组的 [0, i] 这个子区间内挑选一些正整数，每个数只能用一次，使得这些数的和恰好等于 j。

---

状态转移方程：dp[i][j] = dp[i - 1][j] or dp[i - 1][j - nums[i]]

不选择 nums[i]，如果在 [0, i - 1] 这个子区间内已经有一部分元素，使得它们的和为 j ，那么 dp[i][j] = true；
选择 nums[i]，如果在 [0, i - 1] 这个子区间内就得找到一部分元素，使得它们的和为 j - nums[i]。

---

初始条件：dp[0][0] = false，因为候选数 nums[0] 是正整数，凑不出和为 0；
j - nums[i] 一定得保证大于等于 0 ，因此 nums[i] <= j；
j 恰好等于 nums[i]，即单独 nums[i] 这个数恰好等于此时「背包的容积」，也是符合题意的。

---

返回dp[len-1][target]，这里len表示数组的长度，target是数组的元素之和(必须是偶数)的一半

public class LeetCode416 {
   
    public boolean canPartition(int[] nums) {
   
        int sum =
1
2
3
4