P2404 自然数的拆分问题

· · 题解

P2404 自然数的拆分问题

题意：

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

思路：

1.本题属于格子数量不固定的放格子问题

2.后面的数一定要大于等于前面的数，属于组合类题目

3.所有格子放的数的总和必须是n。

CODE：

#include<bits/stdc++.h>
using namespace std;
long long n,sum=0,ans[25];//sum是数的总和，ans数组是格子
void dfs(int x)
{
    if(sum==n)//如果数的总和是n
    {
        for(int i=1;i<=x-2;i++) cout<<ans[i]<<'+';//输出组合方案
        cout<<ans[x-1];//前面输出的只是x-2个数，还要输出ans[x-1]哦！
        cout<<endl;//没输出一种方案，就要换行
        return ;//返回
    }
    for(int i=ans[x-1];i<=n-sum;i++)
    {
     //i从ans[x-1]开始，遍历到总和n-现在的总和（就是剩余的总和）
        if(i==0||i==n) continue;//如果i是0或n,就不能放入格子。
     //因为如果有0，那么组合方案就会出现数字n，但题目说拆分成若干个小于 n 的自然数之和。
     //如果有n,也不行，因为题目说题目说拆分成若干个小于 n 的自然数之和
        ans[x]=i;//第x个格子里放i
        sum+=i;//总和+i
        dfs(x+1);//轮到下一个格子里放数
        ans[x]=false;//下一个格子里没有被放数
        sum-=i;//总和当然要-i了！
    }
}
int main()
{
    cin>>n;//输入n
    dfs(1);//调用自定义搜索函数dfs,只需填一个格子就可以自动填第2个格子，以此类推...
    return 0;//好习惯
}