题目描述输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则按字典序打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。输入描述:输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。
方法:搜索回溯

思路:
本题目是一个全排列问题。且给出的字符串中有重复元素,重复元素之间的顺序只当作一种顺序处理。为了穷举出所有的可能排列顺序,使用回溯法求解:
1、首先假设有n个空格,我们str中取出一个字符依次填入空格,待空格填充完毕,可得到一个字符排列。
2、设回溯函数 backing(vistied, path, result, chars),其中vistied是一个标记数组,标记str中元素是否被访问过。用path存储中间结果
递归函数存在两种情况:
1、若path.length==n,则得到一个排列
2、否则,继续从str中取字符填充。由于本问题是全排列,顺序不同是有意义的。故在从str中取值时,每次都是从str的最开始向后遍历取值,只要未被访问,就可加入

为了解决重复元素的顺序只当作一种,我们将str转为字符数组并排序,之后再取值时,增加一个判断条件,即若第i位的字符与前一位相同的话,只有它的前一位被选取,才可以选择它
要解决重复问题,我们只要设定一个规则,保证在填第 idx 个数的时候重复数字只会被填入一次即可。而在本题解中,我们选择对原数组排序,保证相同的数字都相邻,然后每次填入的数一定是这个数所在重复数集合中「从左往右第一个未被填过的数字」,即如下的判断条件:

if (i > 0 && nums[i] == nums[i - 1] && !vis[i - 1]) {
    continue;
}
public ArrayList<String> Permutation(String str) {
    ArrayList<String> result = new ArrayList<>();
    if (str == null || str.length() == 0) {
        return result;
    }
    char[] chars = str.toCharArray();
    Arrays.sort(chars);
    boolean[] vistied = new boolean[str.length()];
    backing(vistied, new StringBuilder(), result, chars);
    return result;
}


private void backing(boolean[] vistied, StringBuilder path,
                     ArrayList<String> result, char[] chars) {
    if (path.length() == chars.length) {
        result.add(path.toString());
        return;
    }
    for (int i = 0; i < chars.length; i++) {
        if (vistied[i]) {
            continue;
        }
        if (i > 0 && chars[i] == chars[i - 1] && !vistied[i - 1]) {
            continue;
        }
        path.append(chars[i]);
        vistied[i] = true;
        backing(vistied, path, result, chars);
        vistied[i] = false;
        path.delete(path.length() - 1, path.length());
    }
}