组合枚举1

题目描述

写一个递归函数，枚举 1∼n 中取 m 个数的每种方法（组合枚举）。对每种方法把取出的数从小到大排序，若两种方法中前 k−1 个数相同，则第k个数更小的在前。
例如对 n = 4，m = 2，应该按如下顺序给出结果：
{1, 2}，{1, 3}，{1, 4}，{2, 3}，{2, 4}，{3, 4}。

输入格式

输入共 1 行：
第 1 行，2 个正整数 n，m。

输出格式

输出共 m​ 行：
每行一个取法, 按题目要求顺序。

#include <iostream>
using namespace std;

int n, m, cnt = 0, a[25];

void dfs(int step, int last)
{
	if (step > m)
	{
		for (int i = 1; i <= m; i++)
		{
			cout << a[i] << " ";
		}
		cout << endl;
		return;
	}
	
	for (int i = last + 1; i <= n; i++)
	{
		a[step] = i;
		dfs(step + 1, i);
	}
}

int main()
{
	cin >> n >> m;
	dfs(1, 0);
	return 0;
}

组合枚举2 

题目描述

写一个递归函数，枚举 n 个数x1​,⋯,xn​ 中取 m 个数的每种方法（组合枚举）。 对每种方法把取出的数按序号从小到大排序，若两种方法中前 k−1 个数相同，则第 k 个数序号更小的在前。
例如对 n = 4，m = 2，X = {100, 20, 3, 4}，应该按如下顺序给出结果：
{100, 20}，{100, 3}，{100, 4}，{20, 3}，{20, 4}，{3, 4}。

输入格式

输入共 2 行：
第 1 行，2 个正整数 n，m；
第 2 行，n 个正整数 x1​,⋯,xn​。

输出格式

输出共 m​ 行：
每行一个取法, 按题目要求顺序。

#include <iostream>
using namespace std;

int n, m, cnt = 0, a1[35], a2[35];

void dfs(int step, int last)
{
	if (step > m)
	{
		for (int i = 1; i <= m; i++)
		{
			cout << a2[a1[i]] << " ";
		}
		cout << endl;
		return;
	}
	
	for (int i = last + 1; i <= n; i++)
	{
		a1[step] = i;
		dfs(step + 1, i);
	}
}

int main()
{
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
	{
		cin >> a2[i];
	}
	dfs(1, 0);
	return 0;
}