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

 

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

 

示例:

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

 

class Solution {
    List<String>ans = new LinkedList<>();
    char[] c;
    public String[] permutation(String s) {
        c = s.toCharArray();
        dfs(0);
        return ans.toArray(new String[ans.size()]);
    }
    
    public void dfs(int x)
    {
        //base case
        if(x == c.length-1)
        {
            ans.add(String.valueOf(c));
            return;
        }
        HashSet<Character> set = new  HashSet<>();
        //枚举交换产生所有情况
        for(int i = x;i<c.length;i++)
        {
            if(set.contains(c[i]))
                continue;//重复情况进行剪枝
            set.add(c[i]);
            swap(i,x);
            dfs(x+1);
            swap(i,x);//回溯
        }
    }
    
    public void swap(int i,int j)
    {
        char temp = c[i];
        c[i] = c[j];
        c[j] = temp;
    }
}