tasks for today:
1.回溯理论基础
2.77.组合
3.216.组合总和III
4.17.电话号码的字母组合
-------------------------------------------------------------------1.回溯理论基础
- 什么是回溯：在二叉树系列中，我们已经不止一次，提到了回溯，回溯是递归的副产品，只要有递归就会有回溯。所以以下讲解中，回溯函数也就是递归函数，指的都是一个函数
- 回溯法的效率：虽然回溯法很难，很不好理解，但是回溯法并不是什么高效的算法。因为回溯的本质是穷举，穷举所有可能，然后选出我们想要的答案，如果想让回溯法高效一些，可以加一些剪枝的操作，但也改不了回溯法就是穷举的本质。
- 回溯法可以解决的问题：回溯法，一般可以解决如下几种问题：
- 组合问题：N个数里面按一定规则找出k个数的集合
- 切割问题：一个字符串按一定规则有几种切割方式
- 子集问题：一个N个数的集合里有多少符合条件的子集
- 排列问题：N个数按一定规则全排列，有几种排列方式
- 棋盘问题：N皇后，解数独等等
- 理解回溯法：回溯法解决的问题都可以抽象为树形结构，所有回溯法的问题都可以抽象为树形结构。因为回溯法解决的都是在集合中递归查找子集，集合的大小就构成了树的宽度，递归的深度就构成了树的深度。递归就要有终止条件，所以必然是一棵高度有限的树（N叉树）。
- 回溯法模板：
- 回溯函数模板返回值以及参数
回溯算法中函数返回值一般为void。对于参数，因为回溯算法需要的参数不像二叉树递归的时候那么容易一次性确定下来，所以一般是先写逻辑，然后需要什么参数，就填什么参数。
- 回溯函数终止条件
既然是树形结构，就知道遍历树形结构一定要有终止条件。所以回溯也有要终止条件。什么时候达到了终止条件，树中就可以看出，一般来说搜到叶子节点了，也就找到了满足条件的一条答案，把这个答案存放起来，并结束本层递归。
- 回溯搜索的遍历过程
在上面我们提到了，回溯法一般是在集合中递归搜索，集合的大小构成了树的宽度，递归的深度构成的树的深度。
for循环就是遍历集合区间，可以理解一个节点有多少个孩子，这个for循环就执行多少次。
backtracking这里自己调用自己，实现递归。
大家可以从图中看出for循环可以理解是横向遍历，backtracking（递归）就是纵向遍历，这样就把这棵树全遍历完了，一般来说，搜索叶子节点就是找的其中一个结果了。
void backtracking(参数) {
if (终止条件) {
存放结果;
return;
}
for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
处理节点;
backtracking(路径，选择列表); // 递归
回溯，撤销处理结果
}
}
2.77.组合
This practice is good for understanding the back tarcking. If we use search method, there should be k layers loops for finding all the solutions, this will bring complicated embedded code structure, especially when k is large.
Therefore, the back tracking is suitable for this operation, the for-loop traverse in horizon direction while the backtracking function help proceed next level's traverse.
One notable point is the optimization of the algorithm which is branch-cutting. This is caused by the value of k, for example, when n = 4, k = 4, only [1,2,3,4] is valid with startpoint at 1, the [2,3,4] search with start point of 2 is unnecessary. so, these search can be cut by limitting the end index in for-loop.
class Solution:
def combine(self, n: int, k: int) -> List[List[int]]:
result = []
path = []
self.backtracking(n, k, 1, path, result)
return result
def backtracking(self, n, k, startIndex, path, result):
if len(path) == k:
# !!!!!!! path more attention here, this "result.append(path[:])" must use path[:], instead of directly use path, that is because:
# "result.append(path[:])" This appends a copy of the list path to result.
# while, "result.append(path)" This appends a reference to the original list path to result
result.append(path[:])
return
# choose for-loop condition from A or B
# A. this version cut branches
for i in range(startIndex, (n - (k - len(path)) + 1) + 1):
# B. this version does not cut branch:
for i in range(startIndex, n + 1):
path.append(i)
self.backtracking(n, k, i + 1, path, result)
path.pop()3.216.组合总和III
This practice, compared with the practice 77, the main difference is an additional condition which require the sum of the path is n while the length of the path is k. The ordinary backtracking is easy to finish just with an additional condition in terminal logic, as blow:
class Solution:
def combinationSum3(self, k: int, n: int) -> List[List[int]]:
result = []
path = []
self.backtracking(k, n, 1, path, result)
return result
def backtracking(self, k, n, startIndex, path, result):
if len(path) == k and sum(path) == n:
result.append(path[:])
for i in range(startIndex, 10):
path.append(i)
self.backtracking(k, n, i + 1, path, result)
path.pop()The notable point in this practice is the branch cutting operation. there are two condtion that can contribute to the branch cutting which is the sum n and the length k.
Through trail, solely use length k to do cutting will report error, while solely use sum n do cutting can be valid, the best efficiency will be derived by using both the sum n and the length k, as below:
class Solution:
def combinationSum3(self, k: int, n: int) -> List[List[int]]:
result = []
path = []
self.backtracking(k, n, 1, path, result)
return result
def backtracking(self, k, n, startIndex, path, result):
if sum(path) > n:
return
if len(path) == k and sum(path) == n:
result.append(path[:])
return
# when cutting branch, if only use the k do cut, it will report error, this should be used with sum n together.
for i in range(startIndex, (9 - (k - len(path)) + 1) + 1):
path.append(i)
self.backtracking(k, n, i + 1, path, result)
path.pop()
# in this practice, the branch cutting would be better if the condition is the sum instead of the number k, because, there might be the sum reach n frist while the number is still less than k, then it is unnecessary to keep searching4.17.电话号码的字母组合
IN this practice, if there are n digits, then there woule be n set of letters, each set containing 3 letters, the target is to find all the letters combination, each element in the combination comes from a different digit's set
In this practice, the termination condition is reaching the length of digits str.
each for-loop traverse's length is decided by the size of the corresponding letter set of the digits, which do not involve branch cutting, the startIndex in this practice is used to decide which digit's set is being traversed.
The difference between this practice and the previous two combinarion problem is that, the previous two practice is finding combination from one single set, while in this practice, the combination's elements come from different set. This make difference in the definition of the startIndex.
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
result = []
path = []
letterMap = {
'0': "",
'1': "",
'2': "abc",
'3': "def",
'4': "ghi",
'5': "jkl",
'6': "mno",
'7': "pqrs",
'8': "tuv",
'9': "wxyz",
}
self.backtracking(digits, 0, letterMap, path, result)
return result
# pay attention to the startIndex, it means different from the previous combination finding problem
def backtracking(self, digits, startIndex, letterMap, path, result):
if len(path) == len(digits):
if len(digits) == 0:
return
result.append(''.join(path[:]))
return
for i in letterMap[digits[startIndex]]:
path.append(i)
self.backtracking(digits, startIndex + 1, letterMap, path, result)
path.pop()