搜索入门题目_搜索例题

现有 n 个学生, 要分成X1 ,X2 ,...,Xm ,共 m 组(m<=n, X1 ,X2 ,...,Xm 分别表示每组的学生人数),要求对于所有的i < j,Xi <= Xj ,共有多少种分组方案,求出分组方案。

【输入格式】

输入文件：dataa.in

只有一行：两个整数n,m(1<=n<=20 1<m<=10)

【输出格式】

输出文件：dataa.out

输出若干行，第一行是一个整数,表示分组方案数量.下面每行为一种分组方案，按字典序分组输出，每行的数与数之间用一个空格隔开。

【输入样例】

输入文件名： dataa.in

6 3

输出文件名： dataa.out

3 
1 1 4 
1 2 3 
2 2 2 

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<queue>
using namespace std;
int a[10];
int depth,ans;
struct node{
	char p[11];
	
};
queue<node> q;
//还可以用vector来存也可以,不用结构体来存 
 
void dfs(int n,int m,int k) 
{
    if(m==1)
    {
        ans++;
        node c;
        int i;for(i=depth-1;i>0&&a[i]!=0;i--)c.p[i]=a[i];
	c.p[i]=n;q.push(c);
        return;
    }
    a[m-1]=k;
    if(k*2>n) return;
    dfs(n-k,m-1,k);
    dfs(n,m,k+1);
}
 
int main()
{
    freopen("dataa.in","r",stdin);
    freopen("dataa.out","w",stdout);
    int n;
    cin>>n>>depth; 
    dfs(n,depth,1); 
    cout<<ans<<endl;
    while(!q.empty()){
    node p=q.front();
    for( int i=depth-1;i>=0&&p.p[i]!=0;i--)	{
    	printf("%d ",p.p[i]);
	}
		printf("\n");
		q.pop();
	}
    return 0;
}