回溯法

• 与 lc46. 全排列 的不同：需要对同一个节点的子节点剪枝（去重）

# -*- coding:utf-8 -*-
class Solution:
    def Permutation(self, ss):
        # write code here
        def dfs(ss,size,depth,path,used,res):
            if depth==size:
                res.append(''.join(path))
                return
            depth_set=set() # 父节点的所有孩子节点的值
            for i in range(size):
                if not used[i]:
                    if ss[i] in depth_set:continue # 剪枝
                    depth_set.add(ss[i])
                    used[i]=True
                    path.append(ss[i])
                    dfs(ss,size,depth+1,path,used,res)
                    used[i] = False
                    path.pop()

        size = len(ss)
        ss = list(ss)
        if size == 0:return []
        if size ==1 : return [ss[0]]

        res = []
        used  = [False]*size
        dfs(ss,size,0,[],used,res)
        return res