题解 | 字符串的排列- 无需排序

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param str string字符串 
     * @return string字符串ArrayList
     */
     ArrayList<String> res = new ArrayList<>();
    public ArrayList<String> Permutation (String str) {
        // write code here
        boolean[] visited = new boolean[str.length()]; //  此数组控制纵向深度
        backTrace(str, visited, new StringBuilder());
        return res;
    }

    private void backTrace(String s, boolean[] visited, StringBuilder sb) {
        if (s.length() == sb.length()) {
            res.add(sb.toString());
            return;
        }
        boolean[] used = new boolean[57]; // 大小写字母集合 此数组控制横向选择 因此范围是控制每个可选
        for (int i=0; i<s.length(); i++) {
            char c = s.charAt(i);
            if (visited[i]) continue;
            if (used[c - 'A']) continue;
            sb.append(c);
            visited[i] = true;
            used[c - 'A'] = true; // 横向选择无需回溯
            backTrace(s, visited, sb);
            visited[i] = false;
            sb.deleteCharAt(sb.length()-1);
        }

    }
}