全排列问题（dfs)c语言

这是一道搜索专题的基础题。

题目描述：
排列与组合是常用的数学方法。
先给一个正整数 ( 1 < = n < = 10 )
例如n＝3，然后输入n个从小到大的数字，例如：1 2 3

所有组合,并且按字典序输出：
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
输入：
输入一个整数n( 1<=n<=10)

1 2 3
输出：
输出所有全排列
每个全排列一行，相邻两个数用空格隔开（最后一个数后面没有空格）
样例输入：
3
样例输出：
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
思路：首先我们肯定明白每个数字只能输出一次，不能多同时也不能少。即我们需要对每一次使用过的数字进行标记，从而达到不重不漏的目的。这个方面处理好了，我们再想一下如何把所有的结果准确无误的输出出来。当然，最容易想得到的就是递归（因为每找出一个数就要使用类似的步骤），比如：第一次输出1、2、3（这个结果很容易实现），但是第二个输出的是1、3、2，最好的方法就是回溯到选出2的步骤，把2换成下一位3。这样，两次结果输出就结束了，然后我们发现以1头的结果输出完了，这时我们需要回溯到选择1的时候，把1换成2，当然，第二个选择的就是1，第三个选择的就是3。这样第三个结果就是2、1、3，以此类推，，，，，，（小编在这里就不再多加赘述了）接下来我们直接来看实现这个功能的代码吧。

void dfs(int x)//x表示的是其中一种情况的第几个数
{
	if(x==n)//说明该情况所需要的数都已经找到
	{
		for(int v=0;v<n;v++)
		{
			printf("%d ",d[v]);
		}
		printf("\n"); //输出
		return ;//结束本次情况
	}
	else
	{
		for(int i=0;i<n;i++)
		{
			if(c[i]==0)
			{
				d[x]=a[i];//对答案数组进行赋值
				c[i]=1;//对选中的数进行标记，防止重复
				dfs(x+1);//递归，开始下一个数字的寻找，如果该情况已经找完，则接着下面运行
				c[i]=0;//清除标记，当然肯定是这个数字在这个位置的结果已经查询完毕
			}
		}
	}
	
}

以上就是实现该功能的核心算法。

将它放在主函数中运行一下看看。

#include<stdio.h>
int a[10],c[10],n,d[10];//c数组对出现过的数字进行标记，d数组为记录答案的数组
void dfs(int i);
int main()
{
	scanf("%d",&n);
	for(int i=0;i<n;i++)
	{
		c[i]=0;//对计数数组进行初始化
	}
	for(int i=0;i<n;i++)
	{
		scanf("%d",&a[i]);
	}
	dfs(0);
}
void dfs(int x)
{
	if(x==n)
	{
		for(int v=0;v<n;v++)
		{
			printf("%d ",d[v]);
		}
		printf("\n"); 
		return ;
	}
	else
	{
		for(int i=0;i<n;i++)
		{
			if(c[i]==0)
			{
				d[x]=a[i];
				//printf("%d ",a[i]);
				c[i]=1;
				dfs(x+1);
				c[i]=0;
			}
		}
	}
	
}

测试样例：

3

1 2 3

输入样例：

4

1 2 3 4

?

?以上就是对全排列问题的解法，最后祝大家编程能力步步高升。