算法1

注意：
① 先找到dfs的输入参数要哪些：1-n个数，那么需要n；当前层数cur、存储path
然后发现1,2,3需要都出现一次，而且出现过的不能再出现了，所以需要seen。
② 写dfs时候，先写终止条件if(){// 结束这个if时候需要return}
③ if以后需要一个for（//遍历路径上的元素）
④ for()内部先写if（）过滤掉不合适的元素，对于合适的元素更新标记seen
⑤ 更新path，然后进入下一层dfs
⑥ 考虑下一层dfs的参数，len不动；seen，path更新过了，直接传入；cur传入什么呢？cur含义是下一层，cur应该cur+1,不应该是i+1或者是cur；对于i+1，那么for中i在不断增加的其不能表示当前层的下一层的含义；对于cur 当dfs结束时候cur改变了，会影响for循环path[cur] = i这一步。

public static void dfs(int len, int cur,boolean[] seen, int[] path){
    if(cur == len){
        for(int i = 1; i < path.length; i++)
            System.out.print(path[i] + " ");
        System.out.println();
        return;
    }

    for(int i = 1; i < len; i++){
        if(seen[i])continue;
        seen[i] = true;
        path[cur] = i;
        dfs(len, cur+1, seen, path);
        seen[i] = false;
    }
}

// 完整代码
import java.util.*;

public class Main{

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] path = new int[n+1];
        boolean[] seen = new boolean[n+1];    
        dfs(n+1, 1, seen,path);
    }

    public static void dfs(int len, int cur,boolean[] seen, int[] path){
        if(cur == len){
            for(int i = 1; i < path.length; i++)
                System.out.print(path[i] + " ");
            System.out.println();
            return;
        }

        for(int i = 1; i < len; i++){
            if(seen[i])continue;
            seen[i] = true;
            path[cur] = i;
            dfs(len, cur+1, seen, path);
            seen[i] = false;
        }
    }
}