将一个正整数n分解成几个正整数相加，可以有多种分解方法，例如7=6+1，7=5+2，7=5+1+1，…。编程求出正整数n的所有整数分解式子。\n\n输入格式：\n每个输入包含一个测试用例，即正整数n (0<

### 回答1：
n<=100)。\n\n输出格式：\n按照每个分解式的字典序排列输出，每个式子占一行，格式为“n=a[1]+a[2]+…+a[k]”，其中a[i]均为正整数。\n\n样例输入：\n7\n\n样例输出：\n7=1+1+1+1+1+1+1\n7=1+1+1+1+1+2\n7=1+1+1+1+3\n7=1+1+1+2+2\n7=1+1+1+4\n7=1+1+2+3\n7=1+1+5\n7=1+2+2+2\n7=1+2+4\n7=1+3+3\n7=1+6\n7=2+2+3\n7=2+5\n7=3+4\n7=7\n\n提示：\n1. 字典序排列是指对于两个分解式，先比较第一个数，如果相同再比较第二个数，以此类推。\n2. 可以使用递归实现。

### 回答2：
本题可以使用递归的方式来求解。具体来说，可以用一个函数来递归分解正整数n，并在每一步中枚举所有可能的加数，直到将n分解成1个正整数。在实现过程中，可以使用一个数组来记录当前的分解式子。

具体实现步骤如下：

1. 编写一个递归函数`dfs(int n, int k)`，其中n表示需要分解的正整数，k表示当前正在处理的加数。我们需要将n分解成若干个不小于k的正整数之和。

2. 在dfs函数中，首先判断是否已经将n分解成1个正整数。如果是，则将当前的分解式子输出。

3. 如果未完成分解，则在当前的分解式子数组中填入加数k，然后递归调用dfs函数，并将n减去k作为新的参数传入，同时k自增1。这样可以保证下一步中的加数大于等于当前加数。

下面是完整的C++代码实现：

#include <iostream>
#include <vector>

using namespace std;

void dfs(int n, int k, vector<int>& res) {
    if (n == 0) {
        for (int i = 0; i < res.size(); i++) {
            if (i > 0) cout << " ";
            cout << res[i];
        }
        cout << endl;
        return;
    }

    for (int i = k; i <= n; i++) {
        res.push_back(i);
        dfs(n - i, i, res);
        res.pop_back();
    }
}

int main() {
    int n;
    cin >> n;

    vector<int> res;
    dfs(n, 1, res);

    return 0;
}

输入格式：
每个输入包含一个测试用例，即正整数n (0<n<30)。

输出格式：
输出所有的分解式子，每个分解式子占一行，各数字间有一个空格，按照从小到大的顺序输出。

### 回答3：
题目描述：

给定一个正整数n，将它分解成多个正整数相加的形式，输出所有的分解式子。

思路分析：

这是一道典型的数据结构和算法问题，我们可以采用回溯法来解决。

回溯算法是一种通过试错的方式来搜索所有的解空间。回溯法当我们发现一个分支的解不能满足要求时，即可放弃此分支，返回上一个分支继续搜索。回溯法在搜索的过程中会剪枝，从而减少不必要的搜索，提高效率。

具体实现：

设置两个函数，一个负责把数字分解成数字相加的形式，一个是主函数。主函数用于输入，分解输出，具体实现时，使用递归来进行分解。为了避免重复，每次分解时，只使用前面已经选中的数字，后面的数字不再选择。

算法实现：

我们先回顾一下递归的特点。

递归是一种函数自己调用自己的方法。

在递归中，一般有两种情况：

递归终止的情况。

递归处理的情况。

这道题中，递归的核心是把输入的正整数从大到小分解为几个正整数之和。

因此，可以设置两个函数：

1. void dfs(int n, int maxn, string path);

其中，dfs函数的作用是分解n为若干个正整数之和，maxn表示分解时，最大的正整数。path表示此次分解的结果，以字符串形式保存。

2. int main();

主函数用于输入测试用例，调用dfs函数，输出所有分解式子。

在dfs函数中，先处理递归终止的情况：

if (n == 0) {
res.push_back(path);
return;
}

表示当n减到了0的时候，我们将分解出的路径，即res数组进行输出，然后直接结束递归。

接下来处理递归处理的情况：

for (int i = min(maxn, n); i >= 1; i--) {
dfs(n - i, i, path + to_string(i) + "+");
}

在循环中，我们枚举数字1到n，每一个数字都可以在分解中出现。我们先用当前数字减去i，得到一个新的数字，然后继续调用dfs函数分解这个新的数字。maxn即为当前数字。

当我们从深度优先搜索中回溯时，需要把原路径上的数字删除。

完整代码如下：