权排列回溯算法

解决一个回溯问题，实际上就是一个决策树的遍历过程。

你只需要思考 3 个问题：

1. 路径：也就是已经做出的选择。
2. 选择列表：也就是你当前可以做的选择。
3. 结束条件：也就是到达决策树底层，无法再做选择的条件。

代码方面，回溯算法的框架：

for 选择 in 选择列表:
    # 做选择
    将该选择从选择列表移除
    路径.add(选择)
    backtrack(路径, 选择列表)
    # 撤销选择
    路径.remove(选择)
    将该选择再加入选择列表

至此，我们就通过全排列问题详解了回溯算法的底层原理。当然，这个算法解决全排列不是很高效，应为对链表使用contains方法需要 O(N) 的时间复杂度。有更好的方法通过交换元素达到目的，但是难理解一些，这里就不写了，有兴趣可以自行搜索一下。

但是必须说明的是，不管怎么优化，都符合回溯框架，而且时间复杂度都不可能低于 O(N!)，因为穷举整棵决策树是无法避免的。这也是回溯算法的一个特点，不像动态规划存在重叠子问题可以优化，回溯算法就是纯暴力穷举，复杂度一般都很高。

leetcode每日推荐

链接:[电话号码的字母组合]

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        dic = {
        '2':['a','b','c'],
        '3':['d','e','f'],
        '4':['g','h','i'],
        '5':['j','k','l'],
        '6':['m','n','o'],
        '7':['p','q','r','s'],
        '8':['t','u','v'],
        '9':['w','x','y','z']
    }
        result = []  # 结果
        res = []    # 没此的便利
        if digits == "":
            return []
        def backtrack(i):
            if i == len(digits):    # 满足条件
                result.append("".join(res)) 
                return
            else:
                for d in dic[digits[i]]:
                    res.append(d)
                    backtrack(i + 1)    # 继续回溯 到满足条件
                    res.pop()        # 吧满足条件的最后一位弹出 继续回溯
        backtrack(0)
        return result