3979 - 2010年中兴面试题
输入两个整数 n 和 m
从数列1，2，3.......n 中 随意取几个数,使其和等于 m
要求将其中所有的可能组合列出来
（每个数后面输出一个空格）
Input
Output
Examples
Input
5 6
Output
2 4 1 5 1 2 3
Solution C++
#include <iostream> using namespace std; #define Max 100 int n,m;//n个数中选出若干数，总和为m int v[Max];//标记n个数是否被选，1选，0不选 void f(int k,int sum) { int i; if(k>n||sum<0) return;//剪枝 if(sum==0) { for(i=0;i<k;i++) if(v[i]) cout<<i+1<<' '; cout<<endl; return; } v[k]=0;//不选第k号 f(k+1,sum);//递归 v[k]=1;//选第k号 f(k+1,sum-k-1);//递归 } int main() { cin>>n>>m; f(0,m); return 0; }