P2404 自然数的拆分 题解

· · 个人记录

**题目描述

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

解析

这个题目特别有意思的的地方就是他要字典序小的在前面，所以递归的方向其实就明确了，要么变大，要么不变。

我们可以把这个数全部拆解成一，然后利用取一，那么就转变成为上面的等式问题了,四个变量y代表的是当前情况下的y，如果变大就+1，但是sum就不变了。但是一共只能走n步，cnt也不变，因为还y没有定下来。

这里会用到n代表你能拆成几个一也代表了你将走几步。

y代表的是我当下要选的数字到底能多大。

sum代表我得把所有数字选进去变成n才可以认为满足。

cnt代表我一共分解成了几个数字。

如果y不变就意味着这个数字定下来，所以加入sum，然后放入cnt，如果不放入，最后输出的时候有问题，当然如果写个分支更好一些! 最后放上代码

#include<bits/stdc++.h>
using namespace std;
int n,ans,k[100];
void dfs(int y,int sum,int step,int cnt)
{
  k[cnt]=y;
  if(step==n)
  {
    if(sum==n&&cnt>1)
    {
      for(int i=0;i<cnt-1;i++)
        cout<<k[i]<<"+";
      cout<<k[cnt-1]<<endl;
    }
    return;
  }
  dfs(y,sum+y,step+1,cnt+1);
  dfs(y+1,sum,step+1,cnt);
}
int main()
{
  cin>>n;
  dfs(1,0,0,0); 
  return 0;
}