回溯1.

什么是回溯法

回溯是一种搜索算法，一般可以用树形结构来表示。

let’s通过例题来理解。

77. 组合

首先看一下暴力算法，也就是nested loops。讲道理暴力算法的时间复杂度没毛病，每个结果正好输出了一次。但问题是代码里要包含k个循环，而k是可变的参数！所以暴力写法只能想想，但并写不出来。

本题回溯的思路如图所示：

77-1

递归的子问题：在给定数组的子数组[startindex:]中选出k个元素加入path中。

递归的base case：k=1的时候将当前path加入到res数组中。

def combine(self, n: int, k: int) -> List[List[int]]:
    res = []
    path = []
    def helper(n, k, startnum):
        nonlocal res
        nonlocal path
        for i in range(startnum, n+1):
            path.append(i)
            if k==1:
                res.append(path.copy())
            else:
                helper(n, k-1, i+1)
            path.pop()
    helper(n, k, 1)
    return res

这题还有一个优化空间，就是如果startnum之后的元素不够下一个k，后面的回溯也不用看了。

举例：n=4, k=4, startnum=0. i如果走到2，下一个helper call就是(4, 3, 3). 但是从3开始只有[3, 4]两个元素，你却想取k=3个元素，那就不对了。所以当n-(i+1)+1 < k-1的时候就不用继续call helper了。

所以将else语句修剪成如下形式：

            else:
                if not n-i < k-1:
                    helper(n, k-1, i+1)

运行用时从300ms变成了40ms！

216. 组合总和 III

和刚才那题是一模一样的做法，只不过判断条件改了一下：

def combinationSum3(self, k: int, n: int) -> List[List[int]]:
    res = []
    path = []
    nine = 9
    def helper(nine, k, startnum):
        nonlocal res, path, n
        for i in range(startnum, nine+1):
            path.append(i)
            if k==1 and sum(path) == n:
                res.append(path.copy())
            else:
                if not nine-i < k-1:
                    helper(nine, k-1, i+1)
            path.pop()
    helper(nine, k, 1)
    return res

17. 电话号码的字母组合

一样的想法，甚至更简单一些。

def letterCombinations(self, digits: str) -> List[str]:
    maps = {"2":"abc", "3":"def", "4":"ghi", "5":"jkl", "6":"mno", "7":"pqrs", "8":"tuv", "9":"wxyz"}
    res = []
    path = []
    def helper(digits):
        if not digits:
            return
        for c in maps[digits[0]]:
            path.append(c)
            if len(digits) == 1:
                res.append("".join(path))
            else:
                helper(digits[1:])
            path.pop()
    helper(digits)
    return res