P2404 自然数的拆分问题

yan_jun · 2022-01-23 10:41:23 · 个人记录

题目链接：https://www.luogu.com.cn/problem/P2404

这题回溯做就行了，但要注意每一层的数都大于等于上一层的数

并且有可能会越界，所以要写一个特判防止爆了使程序提前结束

完整code

#include<bits/stdc++.h>
using namespace std;
int n,a[10000010];
void dfs(int x,int y ,int z){
    if(y>n)return;//当超范围时直接结束 
    if(y==n){//输出 
        //printf("%d=",n);
        for(int i=1;i<z;i++){//z会多1，所以不取等 
            if(i>1)printf("+");
            printf("%d",a[i]);
        }
        printf("\n");
        return ;
    }
    for(int i=x;i<n;i++){
        a[z]=i;//x<=a[z]<n
        dfs(i,y+i,z+1);
    }
}
int main(){
    scanf("%d",&n);
    dfs(1,0,1);
}