本文共 4040 字，大约阅读时间需要 13 分钟。

【思路1】回溯法

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

class Solution:    def permutation(self, s: str) -> List[str]:        c, res = list(s), []        def dfs(x):            if x == len(c) - 1:                res.append(''.join(c)) # 添加排列方案                return            dic = set()            for i in range(x, len(c)):                if c[i] in dic: continue # 重复，因此剪枝                dic.add(c[i])                c[i], c[x] = c[x], c[i] # 交换，将 c[i] 固定在第 x 位                dfs(x + 1) # 开启固定第 x + 1 位字符                c[i], c[x] = c[x], c[i] # 恢复交换        dfs(0)        return res'''作者：jyd链接：https://leetcode-cn.com/problems/zi-fu-chuan-de-pai-lie-lcof/solution/mian-shi-ti-38-zi-fu-chuan-de-pai-lie-hui-su-fa-by/来源：力扣（LeetCode）'''

• 时间复杂度 O(N!) ： N 为字符串 s 的长度；时间复杂度和字符串排列的方案数成线性关系，方案数为 N×(N−1)×(N−2)…×2×1 ，因此复杂度为 O(N!) 。
• 空间复杂度 O(N²) ： 全排列的递归深度为 N ，系统累计使用栈空间大小为 O(N) ；递归中辅助 Set 累计存储的字符数量最多为 N + (N-1) + … + 2 + 1 = (N+1)N/2 ，即占用 O(N²)的额外空间。

【思路2】回溯+回溯

ss：待处理的序列

res：已存入的序列

ans：存放已排序好的字符串

class Solution(object):    def permutation(self, s):        s_list = list(s)        ans = set()        def dfs(ss, res=[]):            if len(ss) == 0:                ans.add("".join(res))                return            for i in range(len(ss)):                dfs(ss[:i]+ss[i+1:], res+[ss[i]])        dfs(s_list, [])        return list(ans)'''作者：fei-ben-de-cai-zhu-UC4q0zhusJ链接：https://leetcode-cn.com/problems/zi-fu-chuan-de-pai-lie-lcof/solution/pythonhui-su-fa-setjie-ti-by-fei-ben-de-cai-zhu-uc/来源：力扣（LeetCode）'''

class Solution:    def permutation(self, s: str) -> List[str]:        if len(s) <=0:            return []        res = list()        self.perm(s,res,'')        uniq = list(set(res))        return sorted(uniq)    def perm(self,ss,res,path):        if ss=='':            res.append(path)        else:            for i in range(len(ss)):                self.perm(ss[:i]+ss[i+1:],res,path+ss[i])

【附】打印版

class Solution:    def permutation(self, s):        c, res = list(s), []        def dfs(x):            # print('固定 x=',x)            if x == len(c) - 1:                print('最后一个字符x =',c[x])                print('排序好的c=',c)                res.append(''.join(c)) # 添加排列方案 遇到终止条件时,才添加最后一个元素                print('此时res=',res)                print()                return            dic = set()            for i in range(x, len(c)):                if c[i] in dic: continue # 重复，因此剪枝                dic.add(c[i])                print('当前字符c[x] =',c[x],end='\t\t')                print('c[%d]=%s'%(i,c[i]),end='\t')                print('i还可取：',[i for i in range(x+1,len(c))])                print('待排序的dic =',dic)                                c[i], c[x] = c[x], c[i] # 交换，将 c[i] 固定在第 x 位                print('# 交换后c =',c)                print('开始c[x+1]=c[%d]=%s的回溯:'%((x+1),c[x+1]))                dfs(x + 1) # 开启固定第 x + 1 位字符                # print('添加后 dic=',dic)                c[i], c[x] = c[x], c[i] # 恢复交换                print('恢复交换c =',c)                print('==='*10)        dfs(0)        return resif __name__ == "__main__":    s = "abc"    print(Solution().permutation(s))

–思路2–

class Solution2(object):    def permutation(self, s):        s_list = list(s)        ans = set()        def dfs(ss, res=[]):            if len(ss) == 0:                ans.add("".join(res))                print('ans=',ans)                print('结束一轮')                return            for i in range(len(ss)):                print('ss=',ss,end='\t')                print('res=',res)                print(ss[:i]+ss[i+1:],res+[ss[i]])                dfs(ss[:i]+ss[i+1:], res+[ss[i]])        dfs(s_list, [])        print(ans)        return list(ans)if __name__ == "__main__":    s = "abc"    print(Solution().permutation(s))

转载地址：http://bfjii.baihongyu.com/