数的拆分dfs解法

利用dfs(深度优先搜索)找到每一种答案
在代码的注释里有详细介绍

#include <iostream>//导入头文件 
using namespace std;//定义命名空间 
int a[100]={1};//防止从0开始拆分陷入死循环 
int num,count=0;//定义num全局变量 count用以计数 
//dfs(n,idx) 拆分数字n，目前已经拆到了第idx个数字 
void dfs(int n,int idx){
	if(n==0){
		//表示数字已经被拆分完毕 
		//输出idx前的数字
		count++;//计数器count增加 
		for(int i=1;i<idx-1;i++){
			cout<<a[i]<<"+";
		} 
		cout<<a[idx-1]<<endl;
	}else if(a[idx-1]>n){
		//前一个已拆分出来的数字，比接下来拆分的
		//总数大，不符合题意，结束 
		return;
	}else{
		//n可以继续被拆分
		//可以被拆分出 a[idx-1]~n 
		for(int i=a[idx-1];i<=n;i++){
			//i 可以从n中拆出来的数字 
			a[idx]=i;
			dfs(n-i,idx+1);
		} 
	}
} 
int main(){
	cin>>num;
	dfs(num,1);//dfs输入数据 
	cout<<"total="<<count;//输出计数器统计数量 
	return 0;
}

孩子最近缺点赞，给个赞吧(球求赞)