image.png

# -*- coding:utf-8 -*-
class Solution:
    def Permutation(self, ss):
        # write code here
        self.ret = []
        if len(ss):
            s = sorted(ss)
            self.book = [0]*len(s)
            self.dfs(s, 0 ,[])
        return sorted(list(set(self.ret)))

    def dfs(self,s, cur, tmp):
        if cur == len(s):
            ans = "".join(tmp)
            self.ret.append(ans)
        else:
            for i in range(len(s)):
                if self.book[i] == 0:
                    tmp.append(s[i])
                    self.book[i] = 1
                    self.dfs(s, cur+1,tmp)
                    self.book[i] = 0
                    del tmp[-1]