Partition Equal Subset Sum（分割等和子集）

题目 / Problem

中文： 给定一个正整数数组 nums，判断能否将它分割成两个子集，使两个子集中元素的总和相等。可以则返回 true，否则返回 false。

English: Given an integer array nums, return true if it can be partitioned into two subsets whose element sums are equal. Otherwise, return false.

示例 / Examples

Example 1

Input:  nums = [1,5,11,5]
Output: true

可以分割为：
It can be partitioned into:

[1,5,5] → sum = 11
[11]     → sum = 11

Example 2

Input:  nums = [1,2,3,5]
Output: false

无法将数组分割成两个元素和相等的子集。
The array cannot be divided into two subsets with equal sums.

约束 / Constraints

1 <= nums.length <= 200
1 <= nums[i] <= 100

问题转化 / Problem Transformation

设数组所有元素之和为 total。如果能分割成两个和相等的子集，那么每个子集的和必须是：
Let total be the sum of all elements. If the array can be split into two equal-sum subsets, each subset must sum to:

target = total / 2

因此问题可以转化为：
The problem becomes:

能否从 nums 中选择一些元素，使它们的和恰好等于 target？
Can we choose some elements from nums whose sum is exactly target?

每个数组元素只能使用一次，因此这是一个典型的 0/1 背包问题。
Each array element may be used only once, making this a classic 0/1 knapsack problem.

总和为奇数时 / When the Total Is Odd

如果 total 是奇数，就不可能平均分成两个整数和，直接返回 false。
If total is odd, it cannot be divided into two equal integer sums, so return false immediately.

if (total % 2 !== 0) {
  return false;
}

解题思路：一维动态规划 / Approach: One-Dimensional DP

定义：
Define:

dp[sum] = 使用已经处理过的元素，能否凑出 sum
dp[sum] = whether processed elements can form the given sum

初始状态 / Base Case

dp[0] = true;

不选择任何元素时，可以凑出总和 0。
Choosing no elements forms a sum of 0.

状态转移 / Transition

处理数字 num 时，如果此前可以凑出 sum - num，加入当前数字后就可以凑出 sum：
When processing num, if sum - num was previously reachable, adding num makes sum reachable:

dp[sum] = dp[sum] || dp[sum - num]

为什么必须倒序更新？ / Why Must We Iterate Backward?

对于每个 num，sum 必须从 target 倒序遍历到 num：
For each num, iterate sum backward from target down to num:

for (let sum = target; sum >= num; sum--) {
  dp[sum] = dp[sum] || dp[sum - num];
}

倒序保证右侧的 dp[sum - num] 仍然是处理当前数字之前的状态，从而让每个元素最多使用一次。
Backward iteration ensures that dp[sum - num] still represents the state before processing the current number, so each element is used at most once.

如果正序更新，当前数字刚产生的新状态可能在同一轮再次被使用，相当于允许无限次选择该数字，错误地变成完全背包。
With forward iteration, a state created by the current number could be reused again in the same pass, incorrectly turning the problem into an unbounded knapsack.

例如，只有数字 2 时：
For example, with only the number 2:

正序更新 / Forward iteration:
dp[2] = dp[0] → true
dp[4] = dp[2] → true  // 同一个 2 被使用了两次 / The same 2 was reused

JavaScript 实现 / JavaScript Implementation

/**
 * @param {number[]} nums
 * @return {boolean}
 */
function canPartition(nums) {
  const total = nums.reduce((sum, num) => sum + num, 0);

  if (total % 2 !== 0) {
    return false;
  }

  const target = total / 2;
  const dp = new Array(target + 1).fill(false);
  dp[0] = true;

  for (const num of nums) {
    // 单个数字超过总和的一半时，不可能进行等和分割
    // Equal partition is impossible if one value exceeds half the total
    if (num > target) {
      return false;
    }

    for (let sum = target; sum >= num; sum--) {
      dp[sum] = dp[sum] || dp[sum - num];
    }

    if (dp[target]) {
      return true;
    }
  }

  return dp[target];
}

执行过程 / Walkthrough

以 nums = [1,5,11,5] 为例：
For nums = [1,5,11,5]:

total  = 22
target = 11

初始时只有和 0 可以凑出：
Initially, only sum 0 is reachable:

可达总和 / Reachable sums: {0}

依次处理数字：
Process each number:

当前数字 / Number	新的可达总和 / Reachable sums
初始 / Initial	`{0}`
`1`	`{0,1}`
`5`	`{0,1,5,6}`
`11`	`{0,1,5,6,11}`

此时 dp[11] = true，已经找到和为 11 的子集 [11]，所以可以提前返回 true。
Now dp[11] is true. A subset summing to 11 has been found, so the function can return true early.

剩余元素自然组成另一个和为 11 的子集 [1,5,5]。
The remaining elements naturally form the other subset [1,5,5], also summing to 11.

为什么找到一个子集就足够？ / Why Is One Subset Enough?

数组总和为 2 × target。只要找到一个和为 target 的子集，所有未被选择的元素总和必然也是：
The total array sum is 2 × target. Once one subset summing to target is found, all unselected elements must also sum to:

2 × target - target = target

因此不需要同时构造两个子集。
Therefore, there is no need to construct both subsets explicitly.

复杂度 / Complexity

设 n = nums.length，target = total / 2。
Let n = nums.length and target = total / 2.

时间复杂度 / Time: O(n × target)
空间复杂度 / Space: O(target)

本题中 total 最大为 200 × 100 = 20000，因此 target 最大为 10000。
Here, total is at most 200 × 100 = 20000, so target is at most 10000.

易错点 / Common Pitfalls

如果总和为奇数，应立即返回 false。
Return false immediately when the total sum is odd.
dp[0] 必须初始化为 true，它是所有状态转移的起点。
Initialize dp[0] to true; it is the starting point for all transitions.
每个数字只能使用一次，所以一维 DP 必须倒序更新。
Each number may be used once, so the one-dimensional DP must iterate backward.
不需要真正构造两个子集，只需判断能否凑出 total / 2。
There is no need to construct both subsets; only test whether total / 2 is reachable.
如果某个 num > target，它无法被放入任一总和为 target 的子集，可以直接返回 false。
If any num > target, it cannot fit into either subset of sum target, so return false immediately.

Partition Equal Subset Sum