nCm

突然だけどnCmを列挙するアルゴリズム


そんなに競技プログラミングやる気なかったけど折角だからICPC出たら組み合わせの総当りで詰み、
その後今日TopCopderやったら組み合わせの総当りで詰んだ。
ということで浅知恵で考えたものをメモしてみる。O(いっぱい)
まあこの程度のアルゴリズム能力ですわ

void comb(vector<vector<int>> *data, int n, int m)
{
	vector<int> kari;
	if(n < m || m==0)
		return;
	if(n == 1)
	{
		kari.push_back(1);
		data->push_back(kari);
		return;
	}

	int bef,af;
	bef = data->size();
	comb(data,n-1,m-1);
	af = data->size();
	if(bef == af)
	{
		kari.push_back(n);
		data->push_back(kari);
	}
	for(int a=bef; a<af; a++)
		(*data)[a].push_back(n);

	comb(data,n-1,m);
}