题解 | 分割等和子集

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = in.nextInt();
        }
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if (sum % 2 != 0) {
            System.out.println("false");
            return;
        }
        int target = sum / 2;
        boolean[] dp = new boolean[target + 1];
        dp[0] = true;
        for (int num : nums) {
            for (int j = target; j >= num; j--) {
                if (dp[j - num]) {
                    dp[j] = true;
                }
            }
        }
        System.out.println(dp[target]);
    }
}

https://www.nowcoder.com/discuss/727521113110073344

思路：

1. 输入处理：读取输入的数组长度和数组元素。
2. 总和计算：计算数组的总和，并检查是否为奇数。如果是奇数，直接输出 false。
3. 动态规划初始化：创建一个布尔数组 dp，大小为 target + 1，并初始化 dp[0] 为 true。
4. 更新动态规划数组：遍历每个元素，反向更新 dp 数组，确保每个元素只被使用一次。
5. 结果输出：检查 dp[target] 的值，如果为 true 则存在符合条件的子集，否则不存在。