输出组合

#include <iostream>
using namespace std;
#define MAX 4
/**
* （组合: C(m,n)）
* 从n个元素中选择m个元素，他们之间没有次序关系
* 以1,2,3,4为例，n=4，m=2。C[]存放组合结果。
* 先确定c[0]=1,然后再从剩下的3(n-i-1)个中选择1(m-1)个。
* 第二轮确定c[0]=2,然后再从剩下的2(n-i-1)个中选择1(m-1)个。
* 直到确定c[0]=3,再往下剩下的元素里面没有m-1个了，不能再选。
*
* 要点：每次都只能选择起始点后面的数字(避免重复),所以设置curPos变量
* a[]: 候选集, n: 大小，m: 选择m个, result[]: 存放组合结果
* curPos:当前选择了a[]中的第curPos个元素
* count:计数，当前选择了几个元素，选到m个之后停止。
*/
void combination(char a[], int n, int m, int curPos, int count, char result[]){
	//选择结束，输出
	if(count == m){
		for(int i=0;i<m;i++){
			cout<<result[i];
		}
		cout<<endl;
	}		
	else{
		//起始点的选择范围是当前起始点curPos后面的所以点
		for(int i=curPos;i<n;i++){
			result[count] = a[i];						//每个后面的元素都尝试
			combination(a, n, m, i+1, count+1, result);	//注意下一个curPos是i+1
		}
	}
}

/**
* （子集）
* 利用求解组合的函数，即可求解子集。
* 子集就是n个元素中分别选择1个，2个，3个...
*/
void sub_set( char a[], int n){
	char c[MAX];
	for(int i=1;i<=n;i++){
		combination(a, n, i, 0, 0, c); //n个元素中选择i个
	}
}

int main(){
	char a[MAX] = {'a' ,'b' ,'c' ,'d' };
	
	cout<<"\n=== 组合 ===" <<endl;
	char result[3];
	combination(a, MAX, 3, 0, 0, result);
	
	cout<<"\n=== 子集 ===" <<endl;
	sub_set(a, MAX);
	return 0;
}