博客

假如有n个数，要从中选出k个数，怎么不重复地输出所有种选择方法呢？

首先要确定一个好的选择策略：

现在有4个数1 2 3 4，要取其中3个

关键是按顺序，我们按顺序先将第一位取为1，现在我们在1之后查找第二位，可以是2，也可以是3

如果第二位是2，那么我们第三位将在2之后寻找——3或4

而如果第三位是3，那么按照顺序，第四位只能是4了。

因此，我们选择的策略是：选择一个数放在第一位，然后选择这个数之后的一个数据放在第二位，然后再选第二个数之后的一个数放在第三位，以此类推，通过循环依次选择数据，我们可以实现不重复地列出所有组合。

其中，依次选数创造不同情况的操作还是由——交换-递归-回溯——实现的。

以上思路整理成代码如下：、

#include <stdio.h>
#include <stdlib.h>
int sum = 0;
int n, k;
int* a;
int dfs(int x, int y)
//x:选择第x位上的数
//y:记录把数组中哪一个数放在x位了，下一次从这里往后选第（x+1）位数
{
	if (x > k)
	{
		for (int i = 1; i <= k; i++)
		{
			printf("%d", a[i]);
		}
		printf("\n");
	}
	else
	{
		for (int i = y + 1; i <= n; i++)
		{
			swap(a, x, i);
			dfs(x + 1, i);
			swap(a, x, i);
			//每次取完数将它交换到a[x]，这样a[x]前k项即为所求
		}
	}
}
int swap(int a[], int m, int n)//交换
{
	int temp = a[m];
	a[m] = a[n];
	a[n] = temp;
}

int main()
{
	scanf("%d%d", &n, &k);
	a = (int*)malloc((n + 1) * sizeof(int));
	for (int i = 1; i <= n; i++)
	{
		scanf("%d", &a[i]);
	}
	dfs(1, 0);//从第一位开始深搜
	free(a);
}

如有错误请指正，谢谢。