回溯算法可以用于解決：
組合問題：N個(gè)數(shù)里面按一定規(guī)則找出k個(gè)數(shù)的集合
切割問題：一個(gè)字符串按一定規(guī)則有幾種切割方式
子集問題：一個(gè)N個(gè)數(shù)的集合里有多少符合條件的子集
排列問題：N個(gè)數(shù)按一定規(guī)則全排列，有幾種排列方式
棋盤問題：N皇后，解數(shù)獨(dú)等等

回溯算法三部曲：
1.回溯函數(shù)模板返回值以及參數(shù)
2.回溯函數(shù)終止條件
3.回溯搜索的遍歷過程

算法框架

void backtracking(參數(shù)) {
    if (終止條件) {
        存放結(jié)果;
        return;
    }

    for (選擇：本層集合中元素（樹中節(jié)點(diǎn)孩子的數(shù)量就是集合的大?。? {
        處理節(jié)點(diǎn);
        backtracking(路徑，選擇列表); // 遞歸
        回溯，撤銷處理結(jié)果
    }
}

for 橫向遍歷（i=1，2，..,),遞歸縱向遍歷
組合問題
77. 組合 - 力扣（Leetcode）

給定兩個(gè)整數(shù) n 和 k，返回范圍 [1, n] 中所有可能的 k 個(gè)數(shù)的組合。
你可以按 任何順序 返回答案。

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)個(gè)節(jié)點(diǎn)直接構(gòu)造結(jié)果，無(wú)需遞歸
            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 

對(duì)于last_index 處理節(jié)點(diǎn)上界的理解：
比如n=15,k=4,len(path)=1時(shí)，接下來(lái)要選3個(gè)數(shù)，遍歷的起點(diǎn)最大是13,最后一個(gè)被選的是[13,14,15]，在這個(gè)時(shí)候14和15開頭的長(zhǎng)度不夠，肯定不符合，就不需要處理可以進(jìn)行剪枝。
比如n=5,k=3,len(path)=0,需要再選3個(gè)數(shù)，遍歷起點(diǎn)最大的數(shù)是3，最后一個(gè)被遍歷的列表是[3,4,5],對(duì)于這個(gè)時(shí)候4和5開頭的就不需要處理了，就是剪枝。
所有可以歸納：
處理節(jié)點(diǎn)上界=n-(k-len(path))+1
所以last_index=n-(k-len(path))+1
而last_index+1則是因?yàn)閞ange區(qū)間左閉右開
這個(gè)問題中n相當(dāng)于樹的寬度，k相當(dāng)于樹的深度。