Java利用DFS递归实现n个样本的全排列_dfs模板java

学习来源

JAVA－DFS实现全排列，感谢该博主的笔记！
下面是我的学习和总结：

DFS递归带回溯的套路伪代码

//author Neuer_桓 2021_03_26
int check(var parameter){
     if(true)//满足条件
         return 1;
     return 0;
    }   
void dfs(int step){
    if satisfy boundary condition{
    //输出结果或保存
    //TODO
    }
    for(int i = 1; i <= n ; i++){
        if (check(i)==0){//判断是否重复
            signal[i] = 1;//标记
            dfs(step+1);
            signal[i]=0;//恢复初始状态，用于回溯
            }
         }
     }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

代码

import java.util.Scanner;

public class DFS {	
	int n;
	int [] array;
	int [] signal;//标记
	
	public DFS(int N) {
		n = N;
		array = new int[n];
		signal = new int[n+1];
	}
    public void dfs(int step) {
    	//达到临界，输出/保存
    	if(step == n) {
    		for(int i = 0; i < n; i++)
    			System.out.print(array[i]+" ");
    		System.out.println();
    	}else if(step < n) {
    		for(int i = 1;i <= n; i++) {
    			if(signal[i] == 0) {//相当于check操作
    				signal[i] = 1;
    				array[step] = i;
    				dfs(step+1);//进行下一步操作
    				signal[i] = 0;//清空标记
    			}
    		}
    	}
    	return;
    }
	public static void main(String[] args) {
		// TODO Auto-generated method stub
        Scanner scan = new Scanner(System.in);
        DFS main = new DFS(scan.nextInt());
        main.dfs(0);
        scan.close();
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

思考和总结

以1-3为例子画DFS的森林图助理解，每一层可以理解为递归中的栈，下图中一共有三层

这道题是求输入一个数N，输出从1~N的全排列，实际上这N个数可以理解为N个样本。子树构成DFS的森林，利用回溯法的思想，结合每一层栈的for循环，我们可以不重复地往每一个子树的叶子遍历，到达叶子后，再回溯（回到上一层栈的for循环）。

结果

3
1 2 3 
1 3 2 
2 1 3 
2 3 1 
3 1 2 
3 2 1 
1
2
3
4
5
6
7