组合型枚举和排列型枚举

一.组合型枚举

1.给两个数字n和m，从1-n中取m个数字的所有情况

方法1：用到了dfs搜索，深度优先搜索每条路径。

//组合形式枚举
//只用组合不用排列
#include<iostream>
using namespace std;
int n,m;
int path[50];
int cnt=0;            //path用来储存当前路径上的数字 
void dfs(int u,int start)
{
	if(u>m)
	{
		for(int i=1;i<=m;i++)
		{
			cout<<path[i]<<" ";
		}
		cout<<endl;
		cnt++;
		return;
	}
	for(int i=start;i<=n;i++)
	{
		path[u]=i;
		dfs(u+1,i+1);      //用递归依次往下取
	}
}
int main()
{
	cin>>n>>m;
	dfs(1,1);
	cout<<cnt<<endl;
	return 0;
 } 

方法2：每个数字都分为选和不选两种情况。

#include<iostream>
#include<vector>
using namespace std;
vector<int>chose; 
int n,m;
void ser(int x )
{
	if(chose.size()>m||chose.size()+(n-x+1)<m)  //剪枝 
		return;//若选择的数超过范围或者已选的和剩下的加在一起不到m 
		       //则不能满足题意，返回。
	if(x>n)    //到底再输出
		{
			for(int i=0;i<chose.size();i++)
				cout<<chose[i];
			cout<<endl;
			return;
		}
	chose.push_back(x);//第x个数选
	ser(x+1);//进入下一层
	chose.pop_back();//第x个数不选
	ser(x+1);//进入下一层
}             
int main()
{
	cin>>n>>m;
	ser(1);//从第1个数开始
}