题解 | #java 回溯+剪枝#

import java.util.ArrayList;
import java.util.Arrays;
public class Solution {

    ArrayList<String> res = new ArrayList<>();
    StringBuffer buffer = new StringBuffer();
    boolean[] visited;

    public ArrayList<String> Permutation(String str) {

        if (str.length() == 0) {
           return res;
       }

        visited = new boolean[str.length()];
        char[] cs = str.toCharArray();

        Arrays.sort(cs); // 排序

        dfs(cs);

        return res;
    }


    private void dfs (char[] cs) {
        if (buffer.length() == cs.length) {
            res.add(buffer.toString());
        }

        for (int i = 0; i < cs.length; i++) {
            if (i > 0 && visited[i - 1] && cs[i] == cs[i - 1]) { // 剪枝（去重），条件：如果上一个字符和这一次的字符相同，跳过
                continue;
            }

            if (!visited[i]) {
                buffer.append(cs[i]);
                visited[i] = true;
                dfs(cs);
                // 回溯
                visited[i] = false;
                buffer.deleteCharAt(buffer.length() - 1);
            }
        }
    }
}