416. 分割等和子集

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

一道经典的 0-1 背包问题 的变形。

📌 题目描述

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

注意：

• 不需要连续
• 每个元素只能用一次
• 两个子集都非空

🔍 思路分析

要分成两个和相等的子集，说明：

• 数组总和 sum 必须是 偶数
• 目标：能否从数组中选出若干数，使其和为 target = sum / 2

这正是 0-1 背包问题：

在容量为 target 的背包中，能否恰好装满？

✅ 解法：动态规划（0-1 背包）

定义状态：

• dp[j] 表示是否能凑出和为 j（布尔值）

初始化：

• dp[0] = true（和为 0 总是可以，不选任何数）

状态转移：

对每个 num，从后往前更新 dp（防止重复使用）：

for (int j = target; j >= num; j--) {
    dp[j] = dp[j] || dp[j - num];
}

最终答案：

• dp[target]

💡 Java 实现

public class Solution {
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for (int num : nums) sum += num;
        
        // 如果总和是奇数，无法平分
        if ((sum & 1) == 1) return false;
        
        int target = sum / 2;
        boolean[] dp = new boolean[target + 1];
        dp[0] = true;
        
        for (int num : nums) {
            // 从后往前遍历，避免重复使用当前 num
            for (int j = target; j >= num; j--) {
                dp[j] = dp[j] || dp[j - num];
            }
        }
        
        return dp[target];
    }
}

⏱️ 复杂度分析

• 时间复杂度：O(n × target)，其中 n = nums.length
• 空间复杂度：O(target)

注意：如果 target 很大（比如超过 10⁴），此方法可能效率低，但本题数据范围通常可接受。

🧪 边界情况处理

• sum 为奇数 → 直接返回 false
• 数组中最大值 > target → 不可能（但 DP 会自动处理，无需显式判断）

✅ 总结