洛谷P2404 自然数的拆分问题

洛谷P2404 自然数的拆分问题

题目描述
任何一个大于1的自然数n，总可以拆分成若干个小于n的自然数之和。现在给你一个自然数n，要求你求出n的拆分成一些数字的和。每个拆分后的序列中的数字从小到大排序。然后你需要输出这些序列，其中字典序小的序列需要优先输出。
首先分析题目，给任意一个数，比如7，要把它拆成小于7的各个数相加，例如1+1+1+1+1+1+1，而且要输出所有序列，这就需要用到搜索，由于拆分后的序列中的数字要按从小到大输出，所以此题应该用深搜。
一开始我想这题的时候，对于深搜如何剪枝，一直不好怎么写。在看了一些大佬的思路后，学习到了一种思路。
下面放代码

#include<iostream>
#include<cstring>
#include<cstdio>
#include<string>
#include<queue>
#include<stack>
#include<algorithm>
#include<vector>
#include<map>
#define MAXN 0x3f3f3f3f
using namespace std;
int a[1000]={1};
void dfs(int m,int t)//兄弟们 开搜了 奥里给！m就是输入的自然数大小，t表示可以拆分自然数的个数
{
    if (m == 0)
    {
        if(t!=2)//如果没有这个，最后会单独输出自然数n
        {cout << a[1];}
        
        for (int i = 2; i <t;i++)//输出拆分的序列
        {
            cout <<'+'<<a[i] ;
        }
        cout << endl;
        return;
    }

    else
    {
        for (int i = a[t - 1]; i <= m;i++)//i=a[t-1]这个操作就很巧妙，首先，题目中说这些序列要从小到大，而a[]这个数组，我们一开始将a初始化为1，后面搜每次都是从a[t]开始,比如第一次搜的是a[1]=2;那么第二次搜就是从a[2]=2开始，也就是说越往后面的序列数，只会大于等于前面的数，而不会小于等于前面的数。
        {
            a[t] = i;
            m -= i;
            dfs(m, t + 1);
            m += i;//回溯 比如搜完了第一个数为1的，从第一个数为2开始 就必须回溯到最开始m的状态。
        }
    }
    
}
int n;
int main()
{
    int n;
    cin >> n;
    dfs(n, 1);
    return 0;
}

还有一种不用回溯的

#include<iostream>
#include<cstring>
#include<cstdio>
#include<string>
#include<queue>
#include<stack>
#include<algorithm>
#include<vector>
#include<map>
#include<cmath>
#define MAXN 0x3f3f3f3f
using namespace std;
int n, m;
int counts =0;
int a[100000]={1};
void dfs(int m,int t )
{
    if(m==0)
    {
        if(t!=2)
            cout << a[1];
        for (int i = 2; i <= t-1;i++)
        {
            cout << '+'<<a[i];
        }
        cout << endl;
    }
    else{
        for (int i = a[t-1]; i <= m;i++)
        {
            a[t] = i;
            dfs(m-a[t], t + 1);//不用回溯
        }
    }
}
int main()
{
    cin >> n;
    dfs(n, 1);
    return 0;
}