递归整数划分问题c++

递归整数划分问题是指将一个正整数n拆分成多个正整数之和的问题。以下是一个C++的递归实现：

#include <iostream>
using namespace std;

void dfs(int s, int t, int n, int num[]) {
    for (int i = num[t - 1]; i <= s; i++) {
        if (i < n) {
            num[t] = i;
            s -= i;
            if (s == 0) {
                for (int j = 1; j <= t; j++) {
                    cout << num[j] << " ";
                }
                cout << endl;
            } else {
                dfs(s, t + 1, i, num);
            }
            s += i;
        }
    }
}

int main() {
    int n;
    cin >> n;
    int num[n];
    num[0] = 1;
    dfs(n, 1, n, num);
    return 0;
}

这个程序中，我们定义了一个dfs函数，其中s表示当前需要拆分的数，t表示当前拆分的步骤，n表示当前拆分的数不能超过n，num数组记录了每一步拆分的数。在dfs函数中，我们首先枚举当前需要拆分的数i，然后判断i是否小于n，如果小于n，则将i记录在num数组中，并将s减去i，然后判断s是否等于0，如果等于0，则说明已经拆分完毕，输出num数组中的数；否则，我们继续递归调用dfs函数，将s、t和i作为参数传入。最后，我们将s加上i，进行回溯，以便产生所有可能产生的拆分。