回溯算法可以用于解决：
组合问题：N个数里面按一定规则找出k个数的集合
切割问题：一个字符串按一定规则有几种切割方式
子集问题：一个N个数的集合里有多少符合条件的子集
排列问题：N个数按一定规则全排列，有几种排列方式
棋盘问题：N皇后，解数独等等
回溯算法三部曲：
1.回溯函数模板返回值以及参数
2.回溯函数终止条件
3.回溯搜索的遍历过程
算法框架
void backtracking(参数) {
if (终止条件) {
存放结果;
return;
}
for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
处理节点;
backtracking(路径，选择列表); // 递归
回溯，撤销处理结果
}
}
for 横向遍历（i=1，2，..,),递归纵向遍历
组合问题
77. 组合 - 力扣（Leetcode）
给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。
class Solution:
def combine(self, n: int, k: int) -> List[List[int]]:
res = []
path = []
def backtracking(n,k,startindex):
if len(path) ==k:
res.append(path[:])
return
# 剪枝， 最后k - len(path)个节点直接构造结果，无需递归
last_index = n-(k-len(path))+1
for i in range(startindex,last_index+1):
path.append(i)
backtracking(n,k,i+1) #递归
path.pop() #回溯
backtracking(n,k,1)
return res
对于last_index 处理节点上界的理解：
比如n=15,k=4,len(path)=1时，接下来要选3个数，遍历的起点最大是13,最后一个被选的是[13,14,15]，在这个时候14和15开头的长度不够，肯定不符合，就不需要处理可以进行剪枝。
比如n=5,k=3,len(path)=0,需要再选3个数，遍历起点最大的数是3，最后一个被遍历的列表是[3,4,5],对于这个时候4和5开头的就不需要处理了，就是剪枝。
所有可以归纳：
处理节点上界=n-(k-len(path))+1
所以last_index=n-(k-len(path))+1
而last_index+1则是因为range区间左闭右开
这个问题中n相当于树的宽度，k相当于树的深度。
