题目：77. 组合
难度：中等
给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。
一、构造回溯
1.填充模板
0.模板
回溯树的最大宽度：n，每一轮可能的数字的个数
回溯树的最大深度：k，组合长度
模板：
void backtracking(参数) {
if (终止条件) {
存放结果;
return;
}
for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
处理节点;
backtracking(路径，选择列表); // 递归
回溯，撤销处理结果
}
}
步骤：1.函数（无返回值，参数多） + 2.if（终止）{收集+return} + 3.for（搜索集）{处理；递归；回溯}
1.函数（无返回值，参数多）
参数：
backtracking(self, n, k, start_idx, path, ans)题目条件：n, k
起始位置：start_idx，用于标记哪些数字已经被访问
结果数组：ans
记录当前组合的数组：path
2.if（终止）{收集+return}
终止条件（回溯深度）：长度：len（组合数组） == k
if len(path) == k:收集结果：组合数组插入结果数组中
ans.append(path[:])不要忘记return，不然会报错超过递归上限
3.for（搜索集）{处理；递归；回溯}
搜索集合（回溯宽度）：起始位置start_idx到n + 1，
其物理意义是所有未访问的数字
for i in range(start_idx, n + 1):处理：组合数组插入元素
path.append(i)递归：起始位置：当前插入的数字 + 1，表示当前插入数字已被访问
self.backtracking(n, k, i + 1, path, ans)回溯：组合数组末尾元素抛出，撤回到上一层的结果
path.pop()2.代码实现
填充模板：
def backtracking(self, n, k, start_idx, path, ans):
if len(path) == k:
ans.append(path[:])
return
for i in range(start_idx, n + 1):
path.append(i)
self.backtracking(n, k, i + 1, path, ans)
path.pop()完整代码（python）：
class Solution:
def backtracking(self, n, k, start_idx, path, ans):
if len(path) == k:
ans.append(path[:])
return
for i in range(start_idx, n + 1):
path.append(i)
self.backtracking(n, k, i + 1, path, ans)
path.pop()
def combine(self, n: int, k: int) -> List[List[int]]:
ans = []
self.backtracking(n, k, 1, [], ans)
return ans二、剪枝优化
1.思路
完全的暴力搜索常常会访问很多废路径，
确切的说就是长度len（path）达不到长度k的路径
组合问题是不能重复访问同一个数字的，
如果某一轮访问了太多的数字，
就会导致路径的后续没有足够的数字使组合数组长度达到k，
这条路径也就作废了，或者说本就不存在这条路径
那如何保证每一条路径都是有效的呢？
解决的方法就是控制每个节点搜索集末端位置
（在n序列中走的最远的路径）
整个搜索集的大小是n
当一条路径到了某个节点，
已经访问的数字的个数是len(path)，
那么还需要访问的次数为(k - len(path))，
所以单个节点搜索集的末端
（回溯树节点内横向按顺序访问，
且每个节点的前端位置不同）
也就是能留给路径上后续节点访问的数字个数最多就是n - (k - len(path))，
也就是某个节点搜索集的末端的长度一旦超过n - (k - len(path))，
该路径的后续步骤就没有足够的节点可以访问了，
所以需要把回溯树的宽度从n调整到n - (k - len(path)) + 1，
末尾的+1是本轮访问的节点
2.实现
完整代码（python）：
class Solution:
def backtracking(self, n, k, start_idx, path, ans):
if len(path) == k:
ans.append(path[:])
return
for i in range(start_idx, n + 1 - (k - len(path) - 1)):
path.append(i)
self.backtracking(n, k, i + 1, path, ans)
path.pop()
def combine(self, n: int, k: int) -> List[List[int]]:
ans = []
self.backtracking(n, k, 1, [], ans)
return ans