java实现 OpenJ_Bailian 4070 全排列

对于数组[1, 2, 3]，他们按照从小到大的全排列是
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
现在给你一个正整数n，n小于8，输出数组[1, 2, …，n]的从小到大的全排列。

Input
输入有多行，每行一个整数。当输入0时结束输入。

Output
对于每组输入，输出该组的全排列。每一行是一种可能的排列，共n个整数，每个整数用一个空格隔开，每行末尾没有空格。

Sample Input
2
3
0

Sample Output
1 2
2 1
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

解题主要思路
深度优先搜索（dfs）

代码

import java.util.*;public class 数字全排列2 {
    private static int n = 0;private static int[] ans;private static boolean[] visited;public static void main(String[] args) {
    Scanner scan = new Scanner(System.in);while((n = scan.nextInt())!= 0) {
    ans = new int[n];visited = new boolean[n];dfs(0);scan.close();}}private static void dfs(int pos) {
    if(pos == n) {
    for(int i = 0; i < n-1; i++) System.out.print(ans[i]+" ");System.out.println(ans[n-1]);return;}for(int i = 0; i < n; i++) {
    if(!visited[i]) {
    ans[pos] = i+1;visited[i] = true;dfs(pos+1);visited[i] = false;}}}
}