[[379493]]

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

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

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

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

回溯算法就登場了。

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

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

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

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

回溯算法模板如下：

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

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