题目 2352: 信息学奥赛一本通T1440-数的划分

解题思路:

将整数n分为k份，任意两份不能相同，而言，我们只需要保证这k个数，每个数都要大于等于前一个数即可。

注意事项:

int a[100]={1};//数组，存放每个值
int n，z;全局变量，方便函数使用
int ans=0;//记录符合条件的组合数

int search(int s,int t){
	int i;
	for(int i=a[t-1];i<=s;i++){//i=a[t-1],即是等于前一个数，从前一个数开始遍历。
		if(i<n){//从这个条件看，仿佛我们只满足了小于n，并没有满足小于s，实际上，我们for循环就将小于s的进行了筛选。
			a[t]=i;
			s-=i;
			if(s==0&&t==z) ans+=1;//如果s=0并且t=z，就是满足了题目的要求，将整数n分为k份。
			else if(t<z&&s>0) search(s,t+1);//需要继续进行搜索的条件
			s+=i;//回溯。
		}
	}
}

此算法还可以用于，按照字典从小到大输出。因为是从小到大遍历的。

参考代码:

#include<bits/stdc++.h>
using namespace std;
int a[100]={1};
int n;
int ans=0;
int z;
int search(int s,int t){
	int i;
	for(int i=a[t-1];i<=s;i++){
		if(i<n){
			a[t]=i;
			s-=i;
			if(s==0&&t==z) ans+=1;
			else if(t<z&&s>0) search(s,t+1);
			s+=i;
		}
	}
}
int main(){
	cin>>n>>z;
	search(n,1);
	cout<<ans;
	return 0;
}