[[379493]]

 回溯算法大家是不是已經(jīng)快忘了，還記得組合問(wèn)題應(yīng)該怎么求了么?哈哈哈

回溯算法其實(shí)就是暴力搜索，既然是暴力搜索為什么要非要用回溯呢?因?yàn)橐恍﹩?wèn)題能暴力搜索出就不錯(cuò)了，找不出更好的辦法。

給定兩個(gè)整數(shù) n 和 k，返回 1 ... n 中所有可能的 k 個(gè)數(shù)的組合。

如果用for循環(huán)嵌套一層一層去解決這個(gè)問(wèn)題，如果n為100，k為50呢，那就50層for循環(huán)，此時(shí)就發(fā)現(xiàn)單純的暴力不可以了。

回溯算法就登場(chǎng)了。

回溯算法中的用遞歸來(lái)做for循環(huán)層疊嵌套(可以理解是開(kāi)k層for循環(huán))

每一次的遞歸中嵌套一個(gè)for循環(huán)，那么遞歸就可以解決多層嵌套循環(huán)的問(wèn)題了。

我在文章回溯算法：求組合問(wèn)題! 中，同時(shí)還給出了回溯三部曲。按照這個(gè)方法來(lái)，就發(fā)現(xiàn)回溯算法其實(shí)并不難咯。

題目鏈接：https://leetcode-cn.com/problems/combinations/

回溯算法模板如下：

void backtracking(參數(shù)) { 
    if (終止條件) { 
        存放結(jié)果; 
        return; 
    } 
 
    for (選擇：本層集合中元素（樹(shù)中節(jié)點(diǎn)孩子的數(shù)量就是集合的大小）) { 
        處理節(jié)點(diǎn); 
        backtracking(路徑，選擇列表); // 遞歸 
        回溯，撤銷(xiāo)處理結(jié)果 
    } 
} 

本文轉(zhuǎn)載自微信公眾號(hào)「代碼隨想錄」，可以通過(guò)以下二維碼關(guān)注。轉(zhuǎn)載本文請(qǐng)聯(lián)系代碼隨想錄公眾號(hào)。