🎈 原创

洛谷 P2404 自然数的拆分问题

题目描述

任何一个大于1的自然数n，总可以拆分成若干个小于n的自然数之和。现在给你一个自然数n，要求你求出n的拆分成一些数字的和。每个拆分后的序列中的数字从小到大排序。然后你需要输出这些序列，其中字典序小的序列需要优先输出。

输入格式

输入：待拆分的自然数n。

输出格式

输出：若干数的加法式子。

输入输出样例

输入 #1

7

输出 #1

1+1+1+1+1+1+1
1+1+1+1+1+2
1+1+1+1+3
1+1+1+2+2
1+1+1+4
1+1+2+3
1+1+5
1+2+2+2
1+2+4
1+3+3
1+6
2+2+3
2+5
3+4

说明/提示

用回溯做。。。。

n\le 8n≤8

---

分析

题目说的很清楚，用回溯做，但是我还是卡住了。就是不知道怎么把重复的去掉。。。

网上搜了题解，发现我没把题目上的每个拆分后的序列中的数字从小到大排序这句话看明白，其实只要在搜索到一个数后判断一下是否大于当前序列最后一个数就可以了。

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

int N;
vector<int> num;

void DFS(int sum);

int main(int argc, const char * argv[])
{
    cin >> N;

    DFS(0);

    return 0;
}

void DFS(int sum)
{
    if(sum == N)
        for(int i = 0; i < num.size(); i++)
            cout << num[i] << (i < num.size() - 1 ? "+" : "\n");
    else if(sum > N)
        return;
    else
    {
        for(int i = 1; i < N; i++)
            if(sum == 0 || i >= num[num.size() - 1])
            {
                num.push_back(i);
                DFS(sum + i);
                num.pop_back();
            }
    }

}