题解 | #字符串的排列#

首先，注意去重，因为字符串的字符中可以重复。

去重有两种：放入结果中去重；得到结果后去重。这两种都可以。

这里使用在放入结果时直接去重，得到去重后的结果。

回溯法：参数和返回值：参数是st，字符串对应的字符数组，不设置起始位置；返回值：void

终结条件：StringBuilder中元素数目达到st的数组长度

单层逻辑：for循环从0开始，首先判断当前元素是否已被使用，未被使用放入，返回弹出

import java.util.*;

public class Solution {
    ArrayList<String> res = new ArrayList<String>();
    StringBuilder sb = new StringBuilder();
    boolean[] used;
    public ArrayList<String> Permutation(String str) {
       char[] st = str.toCharArray();
       Arrays.sort(st);
       used = new boolean[st.length];
       getPermute(st);
        return res;
    }

    public void getPermute(char[] st) {
        if (sb.length() == st.length) {
            res.add(sb.toString());
        }

        for (int i = 0; i < st.length; ++i) {
            if (used[i]) {
                continue;
            }
            // 去重，如果前一个元素跟自己一样，但是它却没被使用，说明在结果序列的这个位置已经放了前一个元素，那么当前就不能用啦，用了结果会重复
            if (i > 0 && !used[i - 1] && st[i] == st[i - 1]) {
                continue;
            }
            sb.append(st[i]);
            used[i] = true;
            getPermute(st);
            sb.deleteCharAt(sb.length() - 1);
            used[i] = false;
        }
    }
}