全排列--3/16

public class top3 {
    //深度优先搜索递归解决全排列的问题
    //深度优先的一般思路，但是为什么？？？
    public static void main(String [] args)
    {
        Scanner sc=new Scanner(System.in);
        //究竟有多少个数字需要全排列（还有就是定义成为全局变量和传递参数来说究竟有什么不一样是不是）
        int n=sc.nextInt();
        int st[]=new int[n];
        int num[]=new int[n];
        //如果t传递1进去，表示从第1位开始，那么这个时候有
        //但是t要作为num的数组的下标，所以只能从0开始
        dfs(0,n,st,num);
    }


    //t表示目前我正在排列的是哪一位的位数
    static void dfs(int t,int n,int st[],int num[]) {
        //终止条件
        if(t==n) {
            //我已经排列到最后一位了，这个时候就是结束
            for(int i=0;i<n;i++)
            {
                System.out.print(num[i]+" ");
            }
            System.out.println();
            return;
        }
        //开辟的数组空间是0-n
        //全排列的数组是1-n
        //实际上的索引是0--(n-1)
        for(int i=1;i<=n;i++)
        {
            if(st[i-1]==0)
            {
                num[t]=i;
                st[i-1]=1;
                dfs(t+1,n,st,num);
                st[i-1]=0;
                num[t]=0;
            }

    }


}


}

还看见一种直接使用交换进行全排列，感觉思路上比这个简单，但是这种应该适合绝大多数的深度优先搜索

利用深度优先搜索

一般模版

static void dfs(参数）  参数一般包含我需要判断的条件，标记数组，记录结果的数组，数组大小

{

if(结束条件）

达到目的之后需要做什么

return;

//循环遍历

for(int i=0;i<n;i++)

{

if(当前元素没有被访问过）

操作

递归

回溯
}

}