递归法

这道题本质就是暴力枚举。如果字符串长度n确定，通过简单循环也能实现，即写n个for循环来枚举，但现在是字符串长度n可变，就需要用递归来实现（体现了递归存在的意义，实现了循环无法实现的“无限循环”或者说动态循环次数）。

实际上，原理跟n个for循环一样：

• 第1个for循环，从n个字符中锁定1个字符
• 第2个for循环，从剩下的n-1个字符中，再锁定一个
• 。。。
• 直到第n个循环，只有一个字符（即递归的回归条件）
• 第n个循环结束，退回到第n-1个循环，继续运行剩余的次数（即递归返回）

# @param str string字符串 
# @return string字符串一维数组
#
class Solution:
    def Permutation(self , subString: str) -> List[str]:
        # 回归条件
        length = len(subString)
        if length <= 1:
            return subString
        # 每次固定一个元素，对剩下的元素再进行全排列，依次递归
        Lists = []
        for i in range(length):
            # 固定一个元素
            preString = subString[i]
            # 剩下的元素继续递归
            subList = self.Permutation(subString[0:i]+subString[i+1:])
            # 解锁：将之前固定的元素和剩下元素的全排列，进行组合
            for j in subList:
                flag = preString + j
                if flag not in Lists:
                    Lists.append(flag)
        # 返回每一层递归组合后的所有结果
        return Lists