题解 | 分割等和子集

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        int n = in.nextInt();
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = in.nextInt();
        }
        System.out.println(canPartitionNew(nums));
    }

    //https://leetcode.cn/problems/NUPfPr/
    public static boolean canPartition(int[] nums) {

        int n = nums.length;
        if (n < 2) {
            return false;
        }
        int sum = 0, maxNum = 0;

        for (int num : nums) {
            sum += num;
            maxNum = Math.max(maxNum, num);
        }

        if (sum % 2 != 0) {
            return false;
        }
        int target  = sum / 2;
        if (maxNum > target) {
            return false;
        }

        // 列从0开始，所以需额外一列表示和为0的列
        //dp[i][j]表示从数组的[0，i]下标范围内选取若干个正整数（可以是0个），是否存在一种选取方案使得被选取的正整数和为j.
        boolean[][] dp = new boolean[n][target + 1];

        //边界问题 ，情况1：不选取任何数，被选取的正整数和为0；情况2：i==0,只有一个正整数nums[0]被选取
        for (int i = 0; i < n; i++) {
            dp[i][0] = true;
        }
        dp[0][nums[0]] = true;

        for (int i = 1; i < n; i++) {
            int num = nums[i];

            for (int j = 1; j <= target; j++) {
                if (j >= num) {
                    //若j>nums[i],则对于当前数字nums[i]而言，可以选择，也可以不选择，两种情况只要一个为true,就有dp[i][j]=true
                    //1,不选择nums[i],dp[i][j]=dp[i-1][j];2,选择nums[i],dp[i][j] = dp[i-1][j-nums[i]],逻辑|，至少一个为真，无论第一个是否为真，第二个都执行
                    dp[i][j] = dp[i - 1][j] | dp[i - 1][j - num];
                } else {
                    //若j<nums[i],则在选取的数字和等于j的情况下无法选取当前数字nums[i],所以dp[i][j] = dp[i-1][j]
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }

        return dp[n - 1][target];

    }

    public static boolean canPartitionNew(int[] nums) {

        int n = nums.length;
        if (n < 2) {
            return false;
        }
        int sum = 0, maxNum = 0;

        for (int num : nums) {
            sum += num;
            maxNum = Math.max(maxNum, num);
        }

        if (sum % 2 != 0) {
            return false;
        }
        int target  = sum / 2;
        if (maxNum > target) {
            return false;
        }

        // 列从0开始，所以需额外一列表示和为0的列
        //每一行的dp值只和上一行的dp有关；
        boolean[] dp = new boolean[target + 1];

        //边界问题 ，情况1：不选取任何数，被选取的正整数和为0；情况2：i==0,只有一个正整数nums[0]被选取

        dp[0] = true;

        for (int i = 0; i < n; i++) {
            int num = nums[i];
            //第2层需要从后往前，如果从前往后，则计算dp[j]值的时候，dp[j-nums[i]]已经被更新过状态了，不是上一行的dp值
            for (int j = target; j >= num; --j) {
                dp[j] = dp[j] || dp[j - num];
            }
            if (dp[target]) {
                return true;
            }
        }

        return dp[target];

    }
}