[[379493]]

 回溯算法大家是不是已經快忘了，還記得組合問題應該怎么求了么?哈哈哈

回溯算法其實就是暴力搜索，既然是暴力搜索為什么要非要用回溯呢?因為一些問題能暴力搜索出就不錯了，找不出更好的辦法。

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

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

回溯算法就登場了。

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

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

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

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

回溯算法模板如下：

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

本文轉載自微信公眾號「代碼隨想錄」，可以通過以下二維碼關注。轉載本文請聯(lián)系代碼隨想錄公眾號。