题解 | 数位染色

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

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String s = in.next();
        List<Integer> digits = new ArrayList<>();
        int sum = 0;
        for (char c : s.toCharArray()) {
            int d = c - '0';
            sum += d;
            digits.add(d);
        }
        if (sum % 2 != 0) {
            System.out.println("No");
            return;
        }
        int target = sum / 2;
        boolean[] dp = new boolean[target + 1];
        dp[0] = true;
        for (int d : digits) {
            if (d > target) continue;
            for (int j = target; j >= d; j--) {
                if (dp[j - d]) {
                    dp[j] = true;
                }
            }
        }
        System.out.println(dp[target] ? "Yes" : "No");
    }
}

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

思路：

1. 输入处理：将输入的正整数转换为字符串，并逐个字符处理，提取各个数位的数字并计算总和。
2. 奇偶判断：如果总和是奇数，直接输出"No"。
3. 动态规划初始化：创建一个布尔数组dp，dp[i]表示是否存在子集的和为i。初始化dp[0]为true。
4. 动态规划过程：遍历每个数位数字，逆序更新dp数组，确保每个数字只能用一次。
5. 结果判断：检查目标值是否可达，如果可达则输出"Yes"，否则输出"No"。