首页 > 代码库 > nyoj 32 组合数

nyoj 32 组合数

组合数

时间限制:3000 ms  |  内存限制:65535 KB

难度:3

描述

找出从自然数1、2、... 、n(0<n<10)中任取r(0<r<=n)个数的所有组合。

输入

输入n、r。

输出

按特定顺序输出所有组合。
特定顺序:每一个组合中的值从大到小排列,组合之间按逆字典序排列。

样例输入

5 3

样例输出

543

542

541

532

531

521

432

431

421

321

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
int num, limit;
int a[12];
bool visit[12];

void DFS(int x, int cur, int deep) //入口、当前层、总层数
{
	if(cur > deep) //结束条件
		return ;
	for(int i = x; i >= 1; --i)
	{
		if(!visit[i])
		{
			visit[i] = true;
			a[cur] = i;
			if(cur == deep)
			{
				for(int i = 1; i <= deep; ++i)
					printf("%d", a[i]);
				printf("\n");
			}
			DFS(i - 1, cur + 1, deep);
			visit[i] = false;
		}
	}
}

int main()
{

	while(~scanf("%d%d", &num, &limit))
	{
		memset(visit, false, sizeof(visit));
		DFS(num, 1, limit);
	}
	return 0;
}        

  

nyoj 32 组合数