算法进阶指南（递归）--- 递归实现组合型枚举

题目链接：递归实现组合型枚举

动态数组：

#include<iostream>
#include<vector>

using namespace std;


int n,m;
vector<int > chosen;

void dfs(int x) {
        //当前选择的个数大于m或者根本就凑不到m个数
	if(chosen.size() > m || chosen.size()+n-x+1 < m) return ;
	if(x == n+1) {
		for(int i=0; i<chosen.size(); i++) {
			cout<<chosen[i]<<" ";
		}
		puts("");
		return ;
	}
	
	//选择x这个值
	chosen.push_back(x);
	dfs(x+1);
	chosen.pop_back();
	
	//不选择x这个值
	dfs(x+1);
}
int main() {
	cin >> n >> m;
	dfs(1);
	return 0;
}

位运算版：

#include<iostream>
#include<vector>

using namespace std;


int n,m;

void dfs(int pos,int sum,int tar) {
	if(sum + n - pos <m) return ;
	if(sum==m) {
		for(int i = 0; i < n; i++) {
			if(tar >> i & 1)
				cout<<i+1<<" ";
		}
		puts(" ");
		return ;
	} 
	dfs(pos+1,sum+1,tar|1<<pos);
	dfs(pos+1,sum,tar);
}
int main() {
	cin >> n >> m;
	dfs(0,0,0);
	return 0;
}