牛客官方题解转化为JAVA版-解法为牛客官方题解，我只是转化为java了而已

回溯法，递归实现。
关于回溯法：
回溯是一种算法思想，可以用递归实现。

递归三部曲：

1. 递归函数的功能：dfs(int pos, string s), 表示固定字符串s的pos下标的字符s[pos]
2. 递归终止条件：当pos+1 == s.length()的时候，终止，表示对最后一个字符进行固定，也就说明，完成了一次全排列
3. 下一次递归：dfs(pos+1, s), 很显然，下一次递归就是对字符串的下一个下标进行固定

import java.util.*;
/**
 * 关于去重：利用HashSet存储即可，自动去重;
 * 字母表顺序输出：转换为ArrayList后，利用Collections.sort(result);自动排序
 *
 * */
public class _22字符串的排列 {
    public ArrayList<String> Permutation(String str) {
        HashSet<String> list = new HashSet<>();
        ArrayList<String> result = new ArrayList<>();
        if (str == null || str.equals("") || str.length() == 0) return result;
        StringBuilder s = new StringBuilder(str);
        Permutation_help(list,s,0);
        Iterator it = list.iterator();
        while(it.hasNext()) {
            String item = (String) it.next();
            result.add(item);
        }
        Collections.sort(result);
        return result;
    }

    private void Permutation_help(HashSet<String> list, StringBuilder s, int pos) {
        if (pos+1 == s.length()) {
            list.add(s.toString());
            return;
        }
        // for循环和swap的含义：对于“ABC”，
        // 第一次'A' 与 'A'交换，字符串为"ABC", pos为0， 相当于固定'A'
        // 第二次'A' 与 'B'交换，字符串为"BAC", pos为0， 相当于固定'B'
        // 第三次'A' 与 'C'交换，字符串为"CBA", pos为0， 相当于固定'C'
        for (int i = pos; i < s.length(); i++) {
            s = swap(s, pos, i);
            Permutation_help(list,s,pos+1);
            s = swap(s, i, pos);
            // 回溯的原因：比如第二次交换后是"BAC"，需要回溯到"ABC"
            // 然后进行第三次交换，才能得到"CBA"
        }
    }

    private StringBuilder swap(StringBuilder s, int id1, int id2) {
        char temp = s.charAt(id1);
        s.setCharAt(id1,s.charAt(id2));
        s.setCharAt(id2,temp);
        return s;
    }
}