38字符串的排列

输入一个字符串，按字典的顺序打印出该字符串中字符的所有排列。例如输入字符串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