输入一个字符串，打印出该字符串中字符的所有排列。
你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。

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

>这道题考察的是全排列，就是将字符所有的组合可能全部打印
>由于考虑到会发生重复的问题，所以我使用的是set集合，在Java中对用HashSet
>这样就不用人工判断是否有重的可能
>全排列的原理就是递归回溯
>首先将字符串转化成字符数组，可操纵对应位置的元素
>举个例子，我们的字符总共有5个
>那么我们首先固定前4位，最后一位只有1种可能，
>然后回溯，也就是前三位仍然固定，最后两位解开，然后交换最后两位的值
>不断的释放前一个位置，然后按位交换
>获取所有的排列结果

class Solution:
    def permutation(self, s: str) -> List[str]:
        def dfs(val,k):
            if len(val)==k:
                res.add(''.join(val))
                return
            for i in range(k,len(s)):
                val[i],val[k]=val[k],val[i]
                dfs(val,k+1)
                val[i],val[k]=val[k],val[i]
        res=set()
        val=list(s)
        dfs(val,0)
        return list(res)

class Solution {
    public HashSet<String> list = new HashSet<String>();
    public String[] permutation(String s) {
        dfs(s.toCharArray(), 0);
    return list.toArray(new String[list.size()]);
    }
    public void dfs(char[] ch, int k) {
    if (k == ch.length) {
      list.add(new String(ch));
      return;
    }
    for (int i = k; i < ch.length; i++) {
      swap(ch, k, i);
      dfs(ch, k + 1);
      swap(ch, k, i);
    }
  }
    public void swap(char[] ch, int i, int j) {
    char temp = ch[i];
    ch[i] = ch[j];
    ch[j] = temp;
  }
}