LeetCode 416：分割等和子集，从目标总和推到 0/1 背包倒序遍历
题目要求 给定一个只包含正整数的数组 nums，判断能不能把所有元素分成两个子集，使两个子集的元素总和相等。 输入与输出 输入：整数数组 nums 输出：如果能平分，返回 True；否则返回 False 每个元素必须放入两个子集之一，不能丢弃，也不能把同一个元素使用两次 示例 输入：nums = [1,5,11,5] 输出：True 解释：[1,5,5] 和 [11] 的总和都是 11 输入：nums = [1,2,3,5] 输出：False 解释：总和是 11，奇数不能平分 输入：nums = [1,1] 输出：True 解释：两个子集分别拿一个 1 约束 按 LeetCode 416 题面： 1 <= nums.length <= 200 1 <= nums[i] <= 100 sum(nums) <= 20000 Step 1：先排除总和为奇数的数组 先问一个还不涉及选数的问题：两个整数子集的和相等时，整个数组的总和必须满足什么条件？ 问题压力 看 nums = [1,2,3,5]。它的总和是 11。如果两个子集的和都叫 x，那么必须有： 2 * x = 11 整数 x 不可能满足这个等式，所以这个输入可以在尝试任何选数之前直接判定为 False。 ...