学步园

/*
第 21 题
2010  年中兴面试题
编程求解：
输入两个整数n和m，从数列 1，2，3.......n  中随意取几个数,
使其和等于 m ,要求将其中所有的可能组合列出来.
*/

#include<iostream>
#include<stdio.h>
using namespace std;

int n,m;

void printResult(int sum[],int n){
	
	int i;
	for(i=0;i<n;i++)
		if(sum[i])
			printf("%3d",i+1);
	printf("\n");
}

void find(int dest,int id,int sum[],int n)
{
	if(dest==0)
		printResult(sum,n);
	if(dest<=0||id==n)
		return;
	find(dest,id+1,sum,n); 
	sum[id]=1;//将id+1加入，标记选择 
	find(dest-id-1,id+1,sum,n);//已选择id，即选择了数字id+1，
							  //所以将m减去id+1 
	sum[id]=0;//回溯 
}

int main()
{
	int sum[50];
	memset(sum,0,sizeof(sum));
	while(scanf("%d%d",&n,&m))
	{
		printf("%d可以下面相加得到：\n",m);
		find(m,0,sum,n);	
	}
	return 0;
}