java版：
/**
* 字符串的排列
* 输入一个字符串，打印出该字符串中字符的所有排列。
* 例如，输入字符串abc，则打印出由字符a, b, c所能排列出的所有字符串abc, acb, bac, bca, cab和cba。
*
* 详解abc全排列:
*
* abc第一次进入方法
* 1，第一层递归
* begin 0 _ _
* i 0 _ _
* 因为i == begin，不交换，递归进入下一层：begin + 1
*
* 2，第二层递归
* begin _ 1 _
* i1 _ 1 _
* 因为i == begin，不交换，递归进入下一层：begin + 1
*
* 3，第三层递归
* begin _ _ 2
* 因为 begin == chs.length - 1，得到一个结果，退回上层递归
*
* 4，第二层递归
* begin _ 1 _
* i1 _ 1 _
* 不交换，进入下次循环
*
* 5，第二层递归中的循环：i1++
* begin _ 1 _
* i1 _ _ 2
* 交换chs[1]，chs[2]，chs变成acb
* 递归进入下一层：begin + 1
*
* 6，第三层递归
* begin _ _ 2
* 因为 begin == chs.length - 1，得到一个结果，退回上层递归
*
* 7，第二层递归
* begin _ 1 _
* i1 _ _ 2
* 执行交换还原，chs又恢复成abc
* 因为i1 == 2，本次循环结束，退回上层递归
*
* 8，第一层递归
* begin 0 _ _
* i 0 _ _
* 不交换，进入下次循环
*
* 9，第一层递归中的循环：i++
* begin 0 _ _
* i _ 1 _
* 交换chs的0和1位，chs变成bac
* 递归进入下一层：begin + 1
*
* 8，第二层递归
* begin _ 1 _
* i1 _ 1 _
* 不交换，递归进入下一层：begin + 1
*
* 9，第三层递归
* begin _ _ 2
* 因为 begin == chs.length - 1，得到一个结果，退回上层递归
*
* 10，第二层递归
* begin _ 1 _
* i1 _ 1 _
* 不交换还原，进入下一次循环
*
* 11，第二层递归中的循环：i++
* begin _ 1 _
* i1 _ _ 2
* 交换chs的1和2位，chs变成bca
* 递归进入下一层
*
* 12，第三层递归
* begin _ _ 2
* 因为 begin == chs.length - 1，得到一个结果，退回上层递归
*
* 13，第二层递归
* begin _ 1 _
* i1 _ _ 2
* 交换还原，chs变成bac
* 因为i1为2，循环结束，退回上层递归
*
* 14，第一层递归
* begin 0 _ _
* i _ 1 _
* 交换还原，chs变成abc
* 开始下一次循环
*
* 15，第一层递归中的循环：i++
* begin 0 _ _
* i _ _ 2
* 因为 i != begin，交换chs的0和2位，chs变成cba
* 递归进入下一层：begin + 1
*
* 16，第二层递归
* begin _ 1 _
* i1 _ 1 _
* 不交换，递归进入下一层：begin + 1
*
* 17，第三层递归
* begin _ _ 2
* 因为 begin == chs.length - 1，得到一个结果，退回上层递归
*
* 18，第二层递归
* begin _ 1 _
* i1 _ 1 _
* 不交换，进入下次循环
*
* 19，第二层递归中的循环：i++
* begin _ 1 _
* i1 _ _ 2
* 交换，chs变为cab
* 递归进入下一层
*
* 20，第三层递归
* begin _ _ 2
* 因为 begin == chs.length - 1，得到一个结果，退回上层递归
*
* 21，第二层递归
* begin _ 1 _
* i1 _ _ 2
* 交换还原，chs变为cba
* 循环结束，返回上层递归
*
* 22，第一层递归
* begin 0 _ _
* i _ _ 2
* 交换还原，chs变为abc
* 循环结束，退出递归
*
*
*
*/
public class StringPermutation {
public static List<String> solution1(String str) {
List<String> list = new ArrayList<>();
permutation(0, str.toCharArray(), list);
Collections.sort(list);
return list;
}
/**
* 固定第一位，排列后面的位
* @param chs
* @param list
* @param begin
*/
private static void permutation(int begin, char[] chs, List<String> list) {
if (begin == chs.length - 1) {
list.add(new String(chs));
return;
}
for (int i = begin; i < chs.length; i++) {
// 如果值相等，不交换
if (i != begin && chs[i] == chs[begin]) {
continue;
}
if (i != begin) swap(chs, begin, i);
permutation(begin + 1,chs, list);
if (i != begin) swap(chs, begin, i);
}
}
}
