算法标签：

动态规划, 搜索, DFS

题解：

如果当做数学题来做的话肯定要超时，因为10^9数量级太大 这题用的构造法，设要求的数中较大的一个为m，则m的位数最多与和相等。设要去掉的是第 k位数字（从左到右依次为0,1……），通过k位将m分成两部分，右边部分肯定和加数的右边相等 且要满足两对应位数字之和的末位与n的对应位相同，例如10=10+0；k位左边部分应与加数错开 一位；枚举k同时搜索k右边的部分，得到右边部分，左边部分可以根据和推算出来 注意搜索右边部分时，注意每一位有可能有两种情况，假设和的某位为2，则加数对应位可能为1 也可能为6

#include <iostream>
#include <cstring>
#include <cstdlib>
using namespace std;

char num[15], s1[1000][15], s2[1000][15];
long n, t;

int decide(char s[], int k, char t1[], char t2[]) {
    int len = strlen(num);
    int i, j, p;
    char temp[15];
    for (i = 0; i <= 9; i++) {
        strcpy(temp, s);
        t1[k] = '0' + i;
        if (temp[k] < t1[k]) {
            t2[k] = temp[k] + 10 - t1[k] + '0';
            p = k - 1;
            if (p >= 0) {
                while (temp[p] == '0')
                    temp[p--] += 9;
                temp[p] -= 1;
            }
        } else
            t2[k] = temp[k] - t1[k] + '0';
        for (j = k - 1; j >= 0; j--) {
            t1[j] = t2[j + 1];
            if (temp[j] < t1[j]) {
                t2[j] = temp[j] + 10 - t1[j] + '0';
                p = j - 1;
                if (p >= 0) {
                    while (temp[p] == '0')
                        temp[p--] += 9;
                    temp[p] -= 1;
                }
            } else
                t2[j] = temp[j] - t1[j] + '0';
        }
        if (t2[0] == '0') {
            t2[len] = '\0';
            t1[len] = '\0';
            if (strcmp(t1, t2) != 0) {
                for (j = 0; j < t; j++) {
                    if (strcmp(s1[j], t1) == 0)
                        return 0;
                }
                strcpy(s1[t], t1);
                strcpy(s2[t++], t2);
            }
        }
    }
    return 0;
}

int init(char s[], int k, int p, char t1[], char t2[]) {
    if (p == k)
        decide(s, k, t1, t2);
    else {
        int j;
        if ((s[p] - '0') % 2)
            return 0;
        else {
            t1[p] = (s[p] - '0') / 2 + '0';
            t2[p] = t1[p];
            init(s, k, p - 1, t1, t2);
            t1[p] = (s[p] - '0' + 10) / 2 + '0';
            t2[p] = t1[p];
            j = p - 1;
            while (j > 0 && s[j] == '0')
                s[j--] += 9;
            s[j] -= 1;
            init(s, k, p - 1, t1, t2);
        }
    }
    return 0;
}

int search(int k) {
    char s[15], t1[15], t2[15];
    strcpy(s, num);
    init(s, k, strlen(s) - 1, t1, t2);
    return 0;
}

int cmp(const void* _ch1, const void* _ch2) {
    char* ch1 = (char*)_ch1;
    char* ch2 = (char*)_ch2;
    return strcmp(ch1, ch2);
}

int cmp1(const void* _ch1, const void* _ch2) {
    char* ch1 = (char*)_ch1;
    char* ch2 = (char*)_ch2;
    return 0 - strcmp(ch1, ch2);
}

int main() {
    while (cin >> n) {
        // 将整数 n 转换为字符串存储在 num 中
        int i = 0;
        while (n > 0) {
            num[i++] = n % 10 + '0';
            n /= 10;
        }
        num[i] = '\0';
        // 反转字符串以得到正确顺序
        for (int j = 0; j < i / 2; j++) {
            char temp = num[j];
            num[j] = num[i - j - 1];
            num[i - j - 1] = temp;
        }

        t = 0;
        for (i = strlen(num) - 1; i >= 0; i--)
            search(i);
        cout << t << endl;
        qsort(s2, t, sizeof(s2[0]), cmp1);
        qsort(s1, t, sizeof(s1[0]), cmp);
        for (i = 0; i < t; i++) {
            if (s1[i][0] == '0')
                cout << s1[i] + 1 << " + " << s2[i] + 2 << " = " << atoi(num) << endl;
            else
                cout << s1[i] << " + " << s2[i] + 1 << " = " << atoi(num) << endl;
        }
    }
    return 0;
}