3种方法+从简到繁 完成 排列

解题思路:

1.暴力法：使用一个数组存输入的4个数，每次去掉其中一个；然后对于剩余3个数，使用2个for循环选择前2个，
最后一个则等于6-i-j-k （考虑互不相等，i、j、k 最大为 3、2、1 ，而数组下标从0开始，所以4个数下标之和为6）；

2.深度搜索dfs法：dfs的作用是输出 m个数 的全排列（主函数中 调用dfs(1)）；考虑输出的顺序，则需要按 从后往前 的顺序依次去掉，并顺序 赋值给b；
若不考虑顺序，则可按照 注解 中的方法，使用flag 标记 某个数是否 被去掉，若是，则将 最后一个下标（m+1） 替换 当前下标（被去掉）。

3.双数组dfs法：改进前一种算法，使其更贴近本题。

注意事项:

1.暴力法：注意每次循环时，需要先判断 该值 与 前面的变量（包括被去掉的i 和 已经遍历的元素）不同；
2.深度搜索dfs法：主函数中，最先 b.push_back(0) （因为下标从1开始，第0个元素无用，但需填充）；最后b.clear() （清空该向量，便于下一次的赋值）；
3.双数组dfs法：注意每次 f[i]=true 并 dfs(2) 后 ，需要 恢复环境 （f[i]=false）。

参考代码:

暴力法：

#include <stdio.h>
int main(){
    int i,j,k;
    int a[4];
    for(i=0;i<4;i++)
        scanf("%d", a + i);
    for(i=3;i>=0;i--)//从后往前除去一个数据，剩下三个排序
        for(j=0;j<4;j++)
            if(j!=i)
                 for(k=0;k<4;k++)
                     if(k!=i&&k!=j)
                     	printf("%d %d %d\n", a[j], a[k], a[6-i-j-k]);//3+2+1=6
    return 0;
}

深度搜索dfs法：

#include<bits/stdc++.h>
using namespace std;
int g[5],a[5],m = 3;
vector<int> b;
bool s[5];
void dfs(int t){
    if(t>m){
		for(int i=1;i<=m;i++)
        	cout<<g[i]<<" ";
        puts("");
        return;
    }
    for(int i=1;i<=m;i++)
        if(!s[i]){
            s[i]=true;
            g[t]=b.at(i);	
            dfs(t+1);
            s[i]=false;
            // g[t]=0;
        }
}
int main(){
	for(int i=1;i<=4;i++)
		cin>>a[i];		
	for(int i=4;i>=1;i--){//从后往前除去一个数据
		b.push_back(0);
		for(int j=1;j<=4;j++)
			if(j != i) //剩下三个赋值给b数组
				b.push_back(a[j]);	
		dfs(1);//放入dfs中得出全排列
		b.clear();
	}	
    return 0;
}

双数组dfs法：

#include <stdio.h>
bool f[5];
int b[5],a[5],r[5];//双数组
void print(int k){
    for(int i=1;i<=k;i++)
    	printf("%d ", r[i]);
    puts("");
}
void dfs(int k){
    for(int i=1;i<=3;i++)
        if(!f[i]){
            r[k]=b[i];
            f[i]=true;          
            if(k<3) //dfs的递进
				dfs(k+1);
            else 
				print(k);
            f[i]=false;
        }
}
int main(){
    for(int i=1;i<=4;i++)
    	scanf("%d", a + i);
    for(int k=4;k>=1;k--){
        int t=0;
        for(int i=1;i<=4;i++)
            if(i!=k){
                t++;
                b[t]=a[i];
            }
        for(int i=1;i<=3;i++){//循环输入完以后dfs,接住第一次dfs
            f[i]=true;
            r[1]=b[i];
            dfs(2);
            f[i]=false;
        }
    }
    return 0;
}

注：若不考虑输出的顺序，则可使用改进的深度搜索dfs法：

#include<bits/stdc++.h>
using namespace std;
int g[5],a[5],m = 3,flag;
bool s[5];
void dfs(int t){
    if(t>m){
		for(int i=1;i<=m;i++)
        	cout<<g[i]<<" ";
        puts("");
        return;
    }
    for(int i=1;i<=m;i++)
        if(!s[i]){
            s[i]=true;
            if(i == flag)
            	g[t]=a[m+1];      		
            else
            	g[t]=a[i];	
            dfs(t+1);
            s[i]=false;
            // g[t]=0;
        }
}
int main(){
	for(int i=1;i<=4;i++)
		cin>>a[i];	
	for(flag=1;flag<=4;flag++)
		dfs(1);
    return 0;
}