416. 分割等和子集

📝 题目描述

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

---

📌 示例

示例 1

输入：

nums = [1,5,11,5]

输出：

true

解释：数组可以分割成 [1, 5, 5] 和 [11]，两者和均为11。

示例 2

输入：

nums = [1,2,3,5]

输出：

false

解释：数组无法分割成两个和相等的子集。

---

🚀 最优解：0-1背包动态规划

🔍 思路解析

问题可转化为 “是否能从数组中选出若干元素，使其和等于数组总和的一半”（即0-1背包问题：背包容量为sum/2，物品重量和价值均为数组元素，判断能否装满背包）。

核心规则：

1. 若数组总和为奇数，直接返回false（无法平分）；
2. 定义dp[i]表示“能否凑出和为i的子集”；
3. 初始状态：dp[0] = true（和为0的子集天然存在）；
4. 状态转移：遍历每个元素num，反向遍历背包容量（避免重复选元素），若dp[j - num] = true，则dp[j] = true。

---

✅ 修正后的完整代码（Java）

你的代码存在逻辑错误（dp.clone()的使用方式），以下是正确实现：

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 读取数组长度
        int n = scanner.nextInt();
        int[] nums = new int[n];

        // 读取数组元素
        for (int i = 0; i < n; i++) {
            nums[i] = scanner.nextInt();
        }

        Solution solution = new Solution();
        boolean result = solution.canPartition(nums);

        System.out.println(result);

        scanner.close();
    }
}

class Solution {
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for (int num : nums) sum += num;
        // 总和为奇数，无法平分
        if (sum % 2 != 0) return false;

        int target = sum / 2;
        boolean[] dp = new boolean[target + 1];
        dp[0] = true; // 初始状态：和为0的子集存在

        // 0-1背包：遍历每个元素，反向遍历容量
        for (int num : nums) {
            // 反向遍历避免重复选取同一元素
            for (int j = target; j >= num; j--) {
                dp[j] = dp[j] || dp[j - num];
            }
        }

        return dp[target];
    }
}

---

🧠 通俗易懂解释

把问题理解为“凑数游戏”：

• 先算数组总和，若总和是奇数，直接出局（比如总和是5，没法分成两个2.5）；
• 若总和是偶数（比如示例1总和是22，目标是凑出11）；
• 逐个拿数组里的数，问“能不能用这些数凑出11”：
  • 拿1：能凑出1；
  • 拿5：能凑出1、5、6（1+5）；
  • 拿11：能凑出1、5、6、11（直接拿11）→ 凑出目标，返回true。

---

⏱ 时间复杂度

O(n × target)

• n：数组长度；
• target：数组总和的一半（最大为(200×100)/2 = 10000）；
• 总操作数为200×10000 = 2×10^6，效率较高。

---

💾 空间复杂度

O(target)

仅使用长度为target+1的布尔数组，空间复杂度为O(10000)（固定大小，可视为常数级）。

---