题解 | #字符串的排列#

含有重复元素的全排列： 排序+剪枝（连续重复元素看作整体使用）

class Solution:
    def Permutation(self , str: str) -> List[str]:
        # write code here
        n = len(str)
        str = sorted(str) # 提前排序
        used = [False]*n
        ret = []
        curr = ''
        def backtrace():
            nonlocal curr # 使用外部嵌套函数的变量
            if len(curr)==n:
#                 ret.append(copy.copy(curr))
                ret.append(curr[:]) # 也可以使用[:]进行拷贝
            for i in range(n):
                if used[i]:
                    continue
                if i>0 and str[i]==str[i-1] and not used[i-1]: # 重复元素，前一个使用时才使用，看作一个整体只使用一次
                    continue
                used[i] = True
                curr += str[i]
                backtrace()
                curr = curr[:-1] # 切片删除字符串尾巴
                used[i] = False
            return
        backtrace()
        return ret