题解 | 数位染色

#include <bits/stdc++.h>
using namespace std;

bool can_split(string& num, int target) {
    int n = num.length();
    vector<vector<bool>> dp(n + 1, vector<bool>(target + 1, false));
    
    // 初始化：空集的和为0
    for(int i = 0; i <= n; i++) {
        dp[i][0] = true;
    }
    
    // 动态规划
    for(int i = 1; i <= n; i++) {
        int digit = num[i-1] - '0';
        for(int j = 0; j <= target; j++) {
            dp[i][j] = dp[i-1][j];  // 不选当前数位
            if(j >= digit) {
                dp[i][j] = dp[i][j] || dp[i-1][j-digit];  // 选当前数位
            }
        }
    }
    
    return dp[n][target];
}

int main() {
    string x;
    cin >> x;
    
    // 计算所有数位之和
    int total = 0;
    for(char c : x) {
        total += c - '0';
    }
    
    // 如果总和为奇数，无解
    if(total % 2 != 0) {
        cout << "No" << endl;
        return 0;
    }
    
    // 判断是否能找到和为total/2的子集
    if(can_split(x, total/2)) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    
    return 0;
}

import java.util.*;

public class Main {
    public static boolean canSplit(String num, int target) {
        int n = num.length();
        boolean[][] dp = new boolean[n + 1][target + 1];
        
        // 初始化：空集的和为0
        for(int i = 0; i <= n; i++) {
            dp[i][0] = true;
        }
        
        // 动态规划
        for(int i = 1; i <= n; i++) {
            int digit = num.charAt(i-1) - '0';
            for(int j = 0; j <= target; j++) {
                dp[i][j] = dp[i-1][j];  // 不选当前数位
                if(j >= digit) {
                    dp[i][j] = dp[i][j] || dp[i-1][j-digit];  // 选当前数位
                }
            }
        }
        
        return dp[n][target];
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String x = sc.next();
        
        // 计算所有数位之和
        int total = 0;
        for(char c : x.toCharArray()) {
            total += c - '0';
        }
        
        // 如果总和为奇数，无解
        if(total % 2 != 0) {
            System.out.println("No");
            return;
        }
        
        // 判断是否能找到和为total/2的子集
        if(canSplit(x, total/2)) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
        
        sc.close();
    }
}

def can_split(digits, target):
    """判断是否能找到一些数位，使其和为target"""
    def dfs(pos, cur_sum):
        if cur_sum == target:
            return True
        if pos == len(digits) or cur_sum > target:
            return False
        # 选择当前数位
        if dfs(pos + 1, cur_sum + int(digits[pos])):
            return True
        # 不选择当前数位
        return dfs(pos + 1, cur_sum)
    
    return dfs(0, 0)

def main():
    x = input().strip()
    # 计算所有数位之和
    total = sum(int(d) for d in x)
    
    # 如果总和为奇数，无解
    if total % 2 != 0:
        print("No")
        return
    
    # 判断是否能找到和为total/2的子集
    if can_split(x, total // 2):
        print("Yes")
    else:
        print("No")

if __name__ == "__main__":
    main()