题解 | #字符串的排列#回溯

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param str string字符串 
# @return string字符串一维数组
#
class Solution:
    def __init__(self) -> None:
        self.res = []
        self.path = []
    def back(self, s, used):
        if len(self.path)==len(s):
            self.res.append(''.join(self.path))
        used_set = set()
        for i in range(len(s)):
            if used[i] or s[i] in used_set:
                continue
            used_set.add(s[i])
            used[i]=1
            self.path.append(s[i])
            self.back(s, used)
            self.path.pop()
            used[i]=0
        

    def Permutation(self , str: str) -> List[str]:
        # write code here
        self.back(str, [0 for i in str])
        return self.res

递归过程中使用used数组记录每个元素是否使用过，因为有重复的元素，为了防止出现重复的排列，在每一层递归使用一个used_set集合，记录这一层使用的元素，防止在一层使用两个一样的元素，避免重复排列产生