A152.数的拆分 题解

这题还是有点坑的，一道不算太普通的深搜（dfs）题，
那他坑在哪里呢？坑在它要是不提示你，你都想不到深搜上。

好，我们来做这题。
刚开始当然要先写个大概出来——

#include<bits/stdc++.h>
using namespace std;
int n,ans;
int a[22];
void dfs(int m,int idxx){
	if(m==0){
		ans++;
		for(int i=1;i<idxx-1;i++){
			cout<<a[i]<<"+";
		}
		cout<<a[idxx-1]<<endl;
	}else if(a[idxx-1]>m){
		return ;
	}else{
		for(int i=a[idxx-1];i<=m;i++){
			a[idxx]=i;
			dfs(m-i,idxx+1);
		}
	}
}
int main(){
	cin>>n;
	dfs(n,1);
	cout<<"total="<<ans;
	return 0;
}

然后他给了我——

我找了半天，没辙了，看了一下AC君的代码，发现没啥不同。
最后我看到了这行——

才知道是初始化的问题，也是很无语。
代码如下——

#include<bits/stdc++.h>
using namespace std;
int n,ans;
int a[22]={1};
void dfs(int m,int idxx){
	if(m==0){//m已经被分完了，直接输出
		ans++;
		for(int i=1;i<idxx-1;i++){
			cout<<a[i]<<"+";//注意格式
		}
		cout<<a[idxx-1]<<endl;//输出最后一个数，换行
	}else if(a[idxx-1]>m){//它拆分下来的数字不可能比总数大
		return ;//所以直接返回
	}else{
		for(int i=a[idxx-1];i<=m;i++){
			a[idxx]=i;
			dfs(m-i,idxx+1);
		}
	}
}
int main(){
	cin>>n;
	dfs(n,1);
	cout<<"total="<<ans;//最后一行不能忘记
	return 0;
}

注释给大家加上了啊！