题目的主要信息：

• 选出一个最高达18位数的整数$nn$十进制中的一些位，这些位数字和等于没选的位的数字和
• 如果可以输出Yes，否则输出No

具体做法：

首先使用连除法将$nn$的每位数字依次记录在数组中，并在这个过程中求得所有位数之和，那我们要找的就是能否在这个数组中找到诺干个数字加起来等于位数之和的一半。

首先排除和为奇数的情况，无法构成一半。然后我们用一个长度为和一半的dp数组，$dp[i]dp[i]$不为0表示和为$ii$的情况是可以被找到的，为0代表找不到，初始化都为0。我们遍历数组中记录的每位数字$sum[i]sum[i]$，每次再遍历sum/2到该数字，如果$dp[j]dp[j]$可以被相加得到，说明$j-sum[i]j-sum[i]$已经得到了，或者在之前的遍历中得到过，于是就有转移方程$dp[j]=dp[j]+dp[j-num[i]]dp[j]\; =\; dp[j]\; +\; dp[j\; -\; num[i]]$，最后我们检查$dp[sum\mathrm{/}2]dp[sum/2]$是否为0即可。

#include<iostream>
#include<vector>
using namespace std;

int main(){
    long long n;
    cin >> n;
    vector<int> num; //记录数每位
    int sum = 0;
    while(n){ //连除法取每位数字
        sum += n % 10; //求所有位数字累加和
        num.push_back(n % 10);
        n /= 10; 
    }
    if(sum % 2){ //数位和为奇数，无法分成两半
        cout << "No" << endl;
        return 0;
    }
    vector<int> dp(sum / 2 + 1, 0); //dp[i]不为0，表示dp[i]可以被选出的数字相加得到
    dp[0] = 1;
    for(int i = 0; i < num.size(); i++){
        for(int j = sum / 2; j >= num[i]; j--)
            dp[j] = dp[j] + dp[j - num[i]]; //能够被这两个数相加得到
    }
    if(dp[sum / 2]) //不为0
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
    return 0;
}

复杂度分析：

• 时间复杂度：$O((lo{g}_{10}n{)}^2)O((log\_\{10\}n)^2)$，$nn$的数位一共有$lo{g}_{10}nlog\_\{10\}n$，其中累加和最坏为$9\ast lo{g}_{10}n9*log\_\{10\}n$，因此两层遍历，复杂度为$O((lo{g}_{10}n{)}^2)O((log\_\{10\}n)^2)$
• 空间复杂度：$O(lo{g}_{10}n)O(log\_\{10\}n)$，辅助数组有记录位数的数组，和dp数组，两个大小都是$O(lo{g}_{10}n)O(log\_\{10\}n)$