字符串全排列是剑指offer上的一道题，由于早期碰到就不是很理解，今天特地整理一下思路

1.递归：

1）对于不存在重复字符的字符串，每个长为n的字符串(a1,a2,...,an)的全排列可以看成是，把每一个字符ai放在第一位，其余字符串全排列的情况的总和。这n种情况的排列互相不重叠。

2）对于存在重复字符的字符串，可以有两种方法实现去重：

①采用set一类的数据结构存储数据结果，重复的结果可以自行消除

②重复的字符，只在第一位一次，即a1与后面不同的字符分别交换位置一次。

递归出口：当前全排列的字符长度为1，返回当前字符串

递归操作：把每一个字符ai放在第一位，递归调用其余字符组成的字符串的全排列函数

//摘自牛客网答案

publicvoidPermutation(char[] chars, intbegin, TreeSet result) {

        if(chars==null|| chars.length==0|| begin<0|| begin>chars.length-1) { return; }

        if(begin == chars.length-1) {

            result.add(String.valueOf(chars)) ;

        }else{

            for(inti=begin ; i<chars.length; i++) {

                swap(chars, begin, i) ;

                Permutation(chars, begin+1, result);

                swap(chars, begin, i) ;

            }

        }

    }

2.非递归

直接思想是，从完全正序到完全逆序，字符串的值（按照字符串比较算法）是不断增大的，先把字符串正序排列，然后不断找到下一个刚好大于当前字符串的值。其基本流程如下：

1.正序排序字符串

2.从后向前找到第一个顺序对即(a1,a2,...ai,aj,...an),ai<aj,如果不存在，结束。

3.从（aj,...,an)之间找到大于ai最小的数ak，交换ai和ak，

4.逆序（aj,..an）,下一个序列（a1,a2,...,ak,an,...,ai,...aj）