DFS 输出从n个数中选m个数的全部情况

#include<bits/stdc++.h>
using namespace std;

int vis[10], n = 4, m = 3;

void dfs (int x, int sum) {
	if (x > n) return ; // 不是 x>=n！！！ // 因为x=n说明轮到了选或不选第n个数，但是没判断此时sum的值  // 还有一种办法是将该语句放在if(sum == m)判断后
	if (sum == m) {
		for (int i = 0;i < n;i ++) 
			if (vis[i]) 
				cout << i << ' ';
		cout << endl;
		return ;
	}
	
	vis[x] = 1;
	dfs (x+1, sum + 1); 
	vis[x] = 0;
	dfs (x+1, sum);
}

int main()
{
	dfs (0, 0);	
	// 0~n-1
	// 从 n 个数中选 m 个数的全部情况。罗列出C(n,m)的全部情况 
	// 使用情形：比较暴力，枚举全部的可能。 

	return 0;
}

整体思路是对于第x个数选还是不选。

这是一个暴力模板，这个与全排列的区别在于，全排列是区分顺序的，而该模板对于选出的m个数是不区分顺序的。

因此，确定方案数的题（蓝桥杯）只有四种可能：

• 普通多层循环
• DFS 暴力枚举
• 全排列（next_permutation）
• 动态规划