c++拆分自然数深搜

以下是C++实现拆分自然数深搜的代码：

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

int n; // 待拆分的自然数
vector<int> path; // 记录当前拆分方案
vector<vector<int>> res; // 记录所有拆分方案

void dfs(int cur, int last) {
    if (cur == n) { // 拆分完成
        res.push_back(path);
        return;
    }
    for (int i = last; i <= n - cur; i++) { // 枚举下一个拆分数
        path.push_back(i);
        dfs(cur + i, i);
        path.pop_back();
    }
}

int main() {
    cin >> n;
    dfs(0, 1);
    sort(res.begin(), res.end()); // 按字典序排序
    for (auto& p : res) {
        for (int i = 0; i < p.size(); i++) {
            cout << p[i];
            if (i != p.size() - 1) cout << "+";
        }
        cout << endl;
    }
    return 0;
}