分割等和子集

/*
 * 思路：
 * 1. 首先计算数组的总和，如果总和不是偶数，则不可能将数组分成两个和相等的子集，直接返回false。
 * 2. 如果总和是偶数，则将问题转换为在数组中找到一个子集，其和等于总和的一半。
 * 3. 使用Java Stream API来简化部分代码。
 * 4. 使用动态规划的方法，定义一个dp数组，其中dp[i]表示是否可以通过数组中的某些元素的和得到i。
 * 5. 初始化dp[0]为true，因为和为0总是可以通过不选择任何元素得到。
 * 6. 遍历数组中的每个元素，从后向前更新dp数组，避免重复使用元素。
 */

import java.util.stream.IntStream;

public class Solution {
    public boolean canPartition(int[] nums) {
        int sum = IntStream.of(nums).sum();
        if (sum % 2 != 0) {
            return false;
        }
        int target = sum / 2;
        boolean[] dp = new boolean[target + 1];
        dp[0] = true;
        for (int num : nums) {
            for (int i = target; i >= num; i--) {
                dp[i] = dp[i] || dp[i - num];
            }
        }
        return dp[target];
    }
}