题解 P2404 【自然数的拆分问题】

Xuan__Yao · 2018-08-01 16:06:43 · 题解

这是一道DFS的题目。

这道题你仔细观察样例，可以发现：输出的数是从小到大的。 所以我们要有一个qs。下一次直接从qs开始枚举；

#include<iostream>
using namespace std;
int n,a[10];
void dfs(int he,int c,int qs){
    if(he==n){
        for(int i=1;i<=c-2;i++){
            cout<<a[i]<<'+';
        }//输出。
        cout<<a[c-1]<<endl;
        return ;
    }
    if(he>n) return;//过头返回。
    for(int i=qs;i<=n-1;i++){
        a[c]=i;//记录输出。
        dfs(he+i,c+1,i);
        a[c]=0;//改回原来的0；
    }
}
int main(){
    cin>>n;
    dfs(0,1,1);
    return 0;
}