题面描述

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

思路

1. 求和判断
   先计算数组所有元素的和 $S$。如果 $S$ 为奇数，则不可能将其分成两个和相等的子集，因此直接返回 $false$。

2. 转换为背包问题
   如果 $S$ 为偶数，那么每个子集的目标和为 $T = \frac{S}{2}$。问题转换为：在数组中是否存在一个子集，其和正好为 $T$。

3. 动态规划求解
   定义状态 $dp[i]$ 表示是否存在子集和等于 $i$。初始状态 $dp[0] = true$（空集和为 $0$）。
   对于数组中的每个元素 $num$，倒序遍历目标和从 $T$ 到 $num$，更新状态：
   $dp[i] = dp[i] \lor dp[i - num]$
   最后判断 $dp[T]$ 是否为 $true$。

代码分析

• 时间复杂度
  内层循环遍历的次数与目标和 $T$ 有关，整体时间复杂度约为 $O(n \times T)$，其中 $n$ 是数组长度。

• 空间复杂度
  只使用了一维数组 $dp$，空间复杂度为 $O(T)$。

• 问题本质分析
  本题本质上是一个 $0/1$ 背包问题，要求是否存在一种选择方式使得部分元素的和达到目标 $T$。利用动态规划可以有效解决此问题。

C++

#include <iostream>
#include <vector>
using namespace std;

// 使用 Solution 类包装功能函数
class Solution {
public:
    // 判断是否可以分割成两个和相等的子集
    bool canPartition(vector<int>& nums) {
        int sum = 0;
        // 计算数组总和 $S$
        for (int num : nums) {
            sum += num;
        }
        // 如果 $S$ 为奇数，则不能分割
        if (sum % 2 != 0) return false;
        int target = sum / 2; // 目标和 $T$
        
        // 动态规划数组，$dp[i]$ 表示是否存在子集和为 $i$
        vector<bool> dp(target + 1, false);
        dp[0] = true; // 空集和为 $0$
        
        // 遍历每个元素
        for (int num : nums) {
            // 倒序遍历保证每个元素只被使用一次
            for (int i = target; i >= num; i--) {
                dp[i] = dp[i] || dp[i - num];
            }
        }
        return dp[target];
    }
};

int main(){
    int x;
    vector<int> nums;
    // 读取输入数据（ACM 模式）
    while (cin >> x) {
        nums.push_back(x);
    }
    Solution sol;
    // 输出结果，符合题目要求的格式
    cout << (sol.canPartition(nums) ? "true" : "false");
    return 0;
}

Python

# 定义 Solution 类，包含判断是否可以分割的方法
class Solution:
    # 判断是否可以分割成两个和相等的子集
    def canPartition(self, nums: list[int]) -> bool:
        total = sum(nums)  # 计算数组总和 $S$
        if total % 2 != 0:
            return False  # 如果 $S$ 为奇数，则不能分割
        target = total // 2  # 目标和 $T$
        
        # 初始化动态规划数组，$dp[i]$ 表示是否存在子集和为 $i$
        dp = [False] * (target + 1)
        dp[0] = True  # 空集和为 $0$
        
        # 遍历数组中的每个元素
        for num in nums:
            # 倒序遍历确保每个元素只使用一次
            for i in range(target, num - 1, -1):
                dp[i] = dp[i] or dp[i - num]
        return dp[target]

if __name__ == "__main__":
    import sys
    # 读取所有输入数据
    nums = list(map(int, sys.stdin.read().split()))
    sol = Solution()
    # 输出结果，符合题目要求的格式
    print("true" if sol.canPartition(nums) else "false")

Java

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    // 判断是否可以分割成两个和相等的子集
    public static boolean canPartition(int[] nums) {
        int sum = 0;
        // 计算数组总和 $S$
        for (int num : nums) {
            sum += num;
        }
        // 如果 $S$ 为奇数，则不能分割
        if (sum % 2 != 0) {
            return false;
        }
        int target = sum / 2;  // 目标和 $T$
        
        // 初始化动态规划数组，$dp[i]$ 表示是否存在子集和为 $i$
        boolean[] dp = new boolean[target + 1];
        dp[0] = true;  // 空集和为 $0$
        
        // 遍历数组中的每个元素
        for (int num : nums) {
            // 倒序遍历保证每个元素只使用一次
            for (int i = target; i >= num; i--) {
                dp[i] = dp[i] || dp[i - num];
            }
        }
        return dp[target];
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        ArrayList<Integer> list = new ArrayList<>();
        // 读取所有输入数据（ACM 模式）
        while (sc.hasNextInt()) {
            list.add(sc.nextInt());
        }
        int[] nums = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            nums[i] = list.get(i);
        }
        // 输出结果，符合题目要求的格式
        System.out.println(canPartition(nums) ? "true" : "false");
    }
}

Leetcode 89.分割等和子集-原题链接

题目内容

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

输入描述

一个只包含正整数的非空数组$nums$

输出描述

如果可以分割返回$true$否则返回$false$

样例1

输入

1 5 11 5

输出

true

说明

数组可以分割成$[1, 5, 5]$ 和$[11]$。

样例2

输入

1 2 3 5

输出

false

说明

数组不能分割成两个元素和相等的子集。

提示：

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