题目

Permutations

排列

描述

In this kata you have to create all permutations of an input string and remove duplicates, if present. This means, you have to shuffle all letters from the input in all possible orders.

在这个kata中，您必须创建输入字符串的所有排列，并删除重复项（如果存在）。这意味着，您必须以所有可能的顺序从输入中洗牌所有字母。

例子

permutations('a'); # ['a']
permutations('ab'); # ['ab', 'ba']
permutations('aabb'); # ['aabb', 'abab', 'abba', 'baab', 'baba', 'bbaa']

思路

首先，一看到排列的问题，我们就应该明白，使用回溯算法，并且从描述中可以看出，这是一个全排列的问题，并且存在重复的项，我们需要去重的
回溯三部曲：

递归参数
处理全排列，是不需要起点参数的，然后需要一个used数组，用来记录已经使用过的元素，然后就是string，就这个两个参数
终止条件
当path的大小等于string的大小的时候，说明我们找到了全排列，那么就可以保存到result中，并且返回
```
# 终止条件
if len(path) == len(string):
    result.append(''.join(path))
    return 
```

单层递归逻辑
这里着重注意的就是去重的问题，如果我们没有去重，会存在很多一样的答案，这不是我想要的，这里就有一个很重要的概念，树层去重，我们可以从树的角度去看这个问题，如果是处在同一层，出现相同的元素的话，那么就会出现重复的答案，如果是同一个树枝上面的，当然是可以出现重复元素的。

# 循环
for i in range(len(string)):
    # 判断这个是否被用了，如果被用了，就跳过，只没有没有被用，才算符合条件
    # 我们从树的结构出发的话
    # used[i - 1] = True,在用一个树枝上使用过，这个是允许的
    # used[i - 1] = False,说明在同一树层上使用过，这个是不允许的，这样会造成重复
    if (i > 0 and string[i] == string[i - 1]) and (used[i - 1] == False):
        continue
    if used[i] == False:
        # 入队
        path.append(string[i])
        # 记录
        used[i] = True
        # 回溯
        backtracking(string,used)
        # 出队
        path.pop()
        # 取消记录
        used[i] = False

全部代码

# 保存结果
result = []
# 保存符合条件的结果
path = []
    
def backtracking(string,used):
    # 终止条件
    if len(path) == len(string):
        result.append(''.join(path))
        return 
    # 循环
    for i in range(len(string)):
        # 判断这个是否被用了，如果被用了，就跳过，只没有没有被用，才算符合条件
        # 我们从树的结构出发的话
        # used[i - 1] = True,在用一个树枝上使用过，这个是允许的
        # used[i - 1] = False,说明在同一树层上使用过，这个是不允许的，这样会造成重复
        if (i > 0 and string[i] == string[i - 1]) and (used[i - 1] == False):
            continue
        if used[i] == False:
            # 入队
            path.append(string[i])
            # 记录
            used[i] = True
            # 回溯
            backtracking(string,used)
            # 出队
            path.pop()
            # 取消记录
            used[i] = False
            
def permutations(string):
    #your code here
    result.clear()
    path.clear()
    used = [0] * len(string)
    # 排序,方便后面的去重
    string = sorted(string)
    backtracking(string,used)
    return result