输入一个字符串，按字典的顺序打印出该字符串中字符的所有排列。例如输入字符串abc，则打印出由字符a、b、c所能排列出来的所有字符串abc、acb、bac、bca、cab和cba。
参考https://leetcode.com/articles/permutations/
def Permutation(string):
"""
@title: 输入一个字符串，按字典的顺序打印出该字符串中字符的所有排列。
@param: List[string], 大小写英文，长度不超过9，可能有重复。
@return: List[List[string]], 打印各种排列
"""
if not string: return None
string_list = [a for a in string]
def backtrack(first=0):
if first == n:
result.append(string_list[:])
else:
for i in range(first, n):
string_list[first], string_list[i] = string_list[i], string_list[first]
backtrack(first + 1)
string_list[first], string_list[i] = string_list[i], string_list[first]
n = len(string_list)
result = []
backtrack()
return result
if __name__ == "__main__":
# functional tests
assert Permutation('abs') == [['a', 'b', 's'], ['a', 's', 'b'], ['b', 'a', 's'], ['b', 's', 'a'], ['s', 'b', 'a'], ['s', 'a', 'b']]
assert Permutation('Ks') == [['K', 's'], ['s', 'K']]
# Robust tests
assert Permutation('') is None
