一本通-1318：【例5.3】自然数的拆分（回溯）

【题目描述】 任何一个大于1的自然数n，总可以拆分成若干个小于n的自然数之和。

当n=7共14种拆分方法：

7=1+1+1+1+1+1+1 7=1+1+1+1+1+2 7=1+1+1+1+3 7=1+1+1+2+2 7=1+1+1+4 7=1+1+2+3 7=1+1+5 7=1+2+2+2 7=1+2+4 7=1+3+3 7=1+6 7=2+2+3 7=2+5 7=3+4

【输入】 输入n。

【输出】 按字典序输出具体的方案。

【输入样例】 7

【输出样例】 7=1+1+1+1+1+1+1 7=1+1+1+1+1+2 7=1+1+1+1+3 7=1+1+1+2+2 7=1+1+1+4 7=1+1+2+3 7=1+1+5 7=1+2+2+2 7=1+2+4 7=1+3+3 7=1+6 7=2+2+3 7=2+5 7=3+4

---

这道题目如果只是单纯的输出方案数的个数，那么可以参考POJ 2229的DP解法，但是本题要求输出所有的具体组合，并且目的是为了练习搜索，所以还是采用回溯框架来解决。

#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>
#include <string>
#include <climits>
#include <cstdio>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <set>
#include <algorithm>

using namespace std;

int n;
vector<int> res(100005);

void DFS(int sum, int k)
{
    for (int i = res[k - 1]; i <= sum; ++i) { //i <= sum保证不会超过sum
        if (i < n) { //之所以是i < n是因为不能存在不分解的情况
            res[k] = i;
            sum -= i;

            if (sum == 0) {
                cout << n << "=";
                for (int index = 1; index <= k; ++index) {
                    cout << res[index];
                    if (index != k) cout << "+";
                }
                cout << endl;
            }
            else DFS(sum, k + 1);

            sum += i;
        }
    }
}

int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n;

    res[0] = 1;
    DFS(n, 1);

    return 0;
}

起始可以发现每一次新搜索的数字都是大于等于前一个数字的。