剑指offer38 字符串排列

1. 终止条件： 当 x = len(c) - 1 时，代表所有位已固定（最后一位只有 11 种情况），则将当前组合 c 转化为字符串并加入 res ，并返回；
2. 递推参数： 当前固定位 x ；
3. 递推工作： 初始化一个 Set ，用于排除重复的字符；将第 x 位字符与 i \in∈ [x, len(c)] 字符分别交换，并进入下层递归；
4. 剪枝： 若 c[i] 在 Set​ 中，代表其是重复字符，因此 “剪枝” ； 将 c[i] 加入 Set​ ，以便之后遇到重复字符时剪枝；
5. 固定字符： 将字符 c[i] 和 c[x] 交换，即固定 c[i] 为当前位字符；
6. 开启下层递归： 调用 dfs(x + 1) ，即开始固定第 x + 1 个字符；
7. 还原交换： 将字符 c[i] 和 c[x] 交换（还原之前的交换）；

作者：jyd 链接：https://leetcode.cn/problems/zi-fu-chuan-de-pai-lie-lcof/solution/mian-shi-ti-38-zi-fu-chuan-de-pai-lie-hui-su-fa-by/ 来源：************ 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

class Solution:

 
    def Permutation(self, str: str):
        self.res = []
        self.path = list(str)
        self.str=str
        self.backtree(0)
        return  self.res

        # write code here
    def backtree(self,startx):
        n = len(self.str)
        if n- 1 == startx :
            self.res.append("".join(self.path))  #每个位置都被固定后
            return
        dic = set()  # 防止重复
        for i in range(startx,len(self.str)):
            if self.path[i] in dic:  # 重复跳过
                continue
            dic.add(self.path[i])
            self.path[i], self.path[startx] = self.path[startx], self.path[i]  # 通过交换位置生城排列
            self.backtree( startx + 1)  # 向下探测
            self.path[startx], self.path[i] = self.path[i], self.path[startx] #回溯恢复