全排列问题——插空法（递归形式）

为了方便大家理解，我尽量写的浅显易懂，同时希望大家把不理解的发到评论中，我会尽所能，帮助你l理解。

欢迎qq进行交流问题： 

　　　　　　本人QQ ：1770115451             算法交流群： 1061907071

题目描述：

　　请编写一个方法，确定某字符串所有的排列组合，给定一个字符串，请返回该字符串的所有排列

　　 例如： “ABC”  的全排列结果为：ABC 、ACB、BAC、BCA、CAB、CBA

　　（题意：就是一个字符串的每一个字符重新排列出的所有的结果）

解题方法：插空法（递归形式）

　　原理：从最底层进行递归，自底向上的进行插空。（不太清楚的朋友可以考虑看一下迭代的形式，因为递归的思维本来就不符合常人逻辑...）

实现步骤：

　　第一步：创建一个用来装返回结果的字符串集合

　　第二步：递归的出口，也就是当n=1的时候，说明递归结束，则添加第一个字符,并返回结果

　　第三步：如果递归没有结束，则继续自底向上进行递归

　　第四步：返回结果

具体代码：

    //递归形式代码
    public static ArrayList<String> permutation(String str,int n){
        //第一步：创建一个用来装返回结果的字符串集合
        ArrayList<String>  a_n =new ArrayList<String>();
        //第二步：递归的出口，也就是当n=1的时候，说明递归结束，则添加第一个字符,并返回结果
        if(n==1){
            a_n.add(str.charAt(0)+"");
            return a_n;
        }
        //第三步：如果递归没有结束，则继续自底向上进行递归
            //1.获取上一层的递归集合
        ArrayList<String>  a_n_1= permutation(str, n-1) ;  
            //2.对上一层的集合进行插空
        char   ch=  str.charAt(n-1);  //获取当前字符
        for(String e:a_n_1){
            a_n.add(ch+e);  //左边插入
            a_n.add(e+ch);  //右边插入
            for(int j=1;j<e.length();j++){ //e字符串中间插入
                a_n.add(e.substring(0,j)+ch+e.substring(j));
            }
        }
        //第四步：返回结果
        return a_n;        
    }