回溯算法可以用于解决：
组合问题：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相当于树的深度。