class Solution {
    List<String> res = new ArrayList<>();
    StringBuilder sb = new StringBuilder();
    boolean[] st;
    public String[] permutation(String S) {
        int n = S.length();
        st = new boolean[n];

        dfs(S, 0);

        return res.toArray(new String[res.size()]);
    }

    public void dfs(String S, int u){
        if(u == S.length()){
            res.add(new String(sb.toString()));
            return ;
        }

        for(int i = 0; i < S.length(); i ++ ){
            if(st[i] != true){
                st[i] = true;
                sb.append(S.charAt(i));
                dfs(S, u + 1);
                sb.deleteCharAt(sb.length() - 1);
                st[i] = false;
            }
        }
    }
}