【leetcode刷刷】回溯：77.组合

77. 组合

1. 第一次专门做回溯，有点难理解。
2. 首先可以理解回溯可以可视化为树的搜索，因此这道题，树的宽度为n，树的深度为k
3. path作为一个参数传入有点难想
4. 回溯没有返回值
5. 剪纸更难想，通过列算式可以勉强得到for的表达式，但是要自己写出来还是有点难

class Solution:def combine(self, n: int, k: int) -> List[List[int]]:# 递归的话，就是取一个数，然后递归为k-1self.output = []self.backtracking(n, k, 1, [])return self.output# start_index表示从哪里开始遍历def backtracking(self, n, k, start_index, path):  # path用来记录遍历的路径if len(path) == k:   # 当路径长度==k时，输出，相当于遍历到了叶子节点self.output.append(path[:])    # 为啥这里时path就不行？for i in range(start_index, n+1):path.append(i)self.backtracking(n,k,i+1,path)path.pop()   # 回溯

剪枝后：

class Solution:def combine(self, n: int, k: int) -> List[List[int]]:result = []  # 存放结果集self.backtracking(n, k, 1, [], result)return resultdef backtracking(self, n, k, startIndex, path, result):if len(path) == k:result.append(path[:])returnfor i in range(startIndex, n - (k - len(path)) + 2):  # 优化的地方path.append(i)  # 处理节点self.backtracking(n, k, i + 1, path, result)path.pop()  # 回溯，撤销处理的节点

需要多做做题，找找感觉