字符串的排列

输入一个字符串，打印出该字符串中字符的所有排列。

你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。

示例:

输入：s = “abc”
输出：[“abc”,”acb”,”bac”,”bca”,”cab”,”cba”]

限制：

1 <= s 的长度 <= 8

暴力加剪枝，回溯

实际可以类比二叉树的先序遍历DFS。不过二叉树有左右，我们可以区分。类比成比如8个字母，则有8层的数，我们每一层都暴力匹配一下所有的8个字母，但是我可以通过记忆知道前面走过的字母。这样就可以去掉一部分暴力。最后走到叶子的时候，回退。

//防止有重复的字母
HashSet<String> stringArrayList = new HashSet<>();

public String[] permutation(String s) {
    dfs(s, 0, new StringBuffer(), new HashSet<>());
    String[] result = new String[stringArrayList.size()];
    return stringArrayList.toArray(result);
}

public void dfs(String s, int cur, StringBuffer stringBuffer, HashSet<Integer> visited) {

    //走到最后一个了，添加
    if (cur == s.length()) {
        stringArrayList.add(stringBuffer.toString());
        return;
    }


    //每一层都尝试一下所有字母
    //类别二叉树，可以区分左右。先左后右。所以这里重试所有的字母
    for (int i = 0; i < s.length(); i++) {

        //如果前面一层这个字母,被访问过了,就只能选下一个
        if (visited.contains(i)) {
            continue;
        }

        //标记访问
        visited.add(i);

        //添加进去，开始进入下一层
        stringBuffer.append(s.charAt(i));
        dfs(s, cur + 1, stringBuffer, visited);

        //回溯,回退到上一层，去掉这一层的标记
        stringBuffer.deleteCharAt(stringBuffer.length() - 1);
        visited.remove(i);
    }

}