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

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

示例:

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

限制：

1 <= s 的长度 <= 8

与 全排列 II 相同

class Solution:
    def permutation(self, s: str) -> List[str]:
        s = list(s)
        lens = len(s)
        ret = []

        def swap(i, j):
            tem = s[i]
            s[i] = s[j]
            s[j] = tem

        def backStack(begin):
            if begin == lens:
                ret.append("".join(s))
                return
            myset = set()
            for i in range(begin, lens):
                if s[i] in myset:
                    continue
                else:
                    myset.add(s[i])
                swap(i, begin)
                backStack(begin + 1)
                swap(i, begin)

        backStack(0)
        return ret