剑指 Offer 38. 字符串的排列

输入一个字符串(可能包含重复字符)，打印出该字符串中字符的所有排列。

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

示例:

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

限制：

1 <= s 的长度 <= 8

思路

回溯算法

python3解法

class Solution:
    def permutation(self, s: str) -> List[str]:
        def backtrack(s, combination):
            if not s:
                ans.append(combination)
            charset = set()
            for i in range(len(s)):
                if s[i] in charset: continue
                backtrack(s[:i] + s[i+1:], combination + s[i])
                charset.add(s[i])
        ans = []
        backtrack(s, "")
        return ans

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/zi-fu-chuan-de-pai-lie-lcof