题解 | 整数求和

因为每个数只能用一次，所以可以类似回溯的算法，或者更像是 DFS 的方法搜全部可能的解决方案即可

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

void backtrace(int n, int m, int start, int& count) {
    if (m == 0) {
        count++;
        return;
    }
    if (m < 0) return;
    if (m - start < 0) return;

    for (int i = start; i <= n; ++i) {
        backtrace(n, m - i, i + 1, count); // 只能用 1 次，所以从 i + 1 开始
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    int count = 0;
    backtrace(n, m, 1, count);

    cout << count << endl;
    return 0;
}