面试题 08.07. 无重复字符串的排列组合

无重复字符串的排列组合。编写一种方法，计算某字符串的所有排列组合，字符串每个字符均不相同。

示例1:

 输入：S = "qwe"
 输出：["qwe", "qew", "wqe", "weq", "ewq", "eqw"]

示例2:

 输入：S = "ab"
 输出：["ab", "ba"]

提示:

字符都是英文字母。
字符串长度在[1, 9]之间。

思路

回溯算法

python3解法

class Solution:
    def permutation(self, S: str) -> List[str]:
        def backtrack(s, combination):
            if not s:
                ans.append(combination)
            for c in s:
                backtrack(s.replace(c, ""), combination + c)
        ans = []
        backtrack(S, "")
        return ans

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/permutation-i-lcci