欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

Java算法排列数字(DFS)

程序员文章站 2022-06-19 16:26:31
给定一个整数n,将数字1~n排成一排,将会有很多种排列方法。现在,请你按照字典序将所有的排列方法输出。输入格式共一行,包含一个整数n。输出格式按字典序输出所有排列方案,每个方案占一行。数据范围1≤n≤71≤n≤7输入样例:3输出样例:1 2 31 3 22 1 32 3 13 1 23 2 1import java.io.*;import java.lang.*;import java.util.*;class Main{...

给定一个整数n,将数字1~n排成一排,将会有很多种排列方法。

现在,请你按照字典序将所有的排列方法输出。

输入格式

共一行,包含一个整数n。

输出格式

按字典序输出所有排列方案,每个方案占一行。

数据范围

1≤n≤71≤n≤7

输入样例:

3 

输出样例:

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
 import java.io.*;
import java.lang.*;
import java.util.*;

class Main{
    static ArrayList<int[]> list = new ArrayList<>();//存储结果集
    static int n = 0;
    static int[] nums = new int[110];
    static boolean[] f = new boolean[110];
    static void dfs(int t){
        if(t == n){
            for(int i = 0; i < n; ++i){
                System.out.print(nums[i] + " ");
            }
            System.out.println();
            return;
        }
        for(int i = 1; i <= n; ++i){
            if(!f[i]){
                f[i] = true;
                nums[t] = i;
                dfs(t + 1);
                //nums[t] = XXX;因为三个位置一定会填满,所以这里可以不用恢复现场,恢复也没问题
                f[i] = false;
            }
        }
    }
    public static void main(String[] args)throws Exception{
        BufferedReader buf = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.valueOf(buf.readLine());
        dfs(0);
    }
}

本文地址:https://blog.csdn.net/StrawberryMuMu/article/details/107898170