【正经题解】数的拆分

#include <iostream>
using namespace std;

int a[100] = {1};
int num, count = 0;

// 拆分数字 n，目前已经拆到了第 idx 个数字
void dfs(int n, int idx) {
    if (n == 0) {
        // 表示数字已经被拆分完毕
        // 输出 idx 前的数字
        count++; // 计数器 count 增加
        for (int i = 1; i < idx - 1; i++) {
            cout << a[i] << "+";
        }
        cout << a[idx - 1] << endl;
    } else if (a[idx - 1] > n) {
        // 前一个已拆分出来的数字，比接下来拆分的总数大，不符合题意，结束
        return;
    } else {
        // n 可以继续被拆分
        // 可以被拆分出 a[idx-1] ~ n
        for (int i = a[idx - 1]; i <= n; i++) {
            // i 可以从 n 中拆出来的数字
            a[idx] = i;
            dfs(n - i, idx + 1);
        }
    }
}

int main() {
    cin >> num;
    dfs(num, 1); // dfs 输入数据
    cout << "total=" << count << endl; // 输出计数器统计数量
    return 0;
}