「经典题目回顾」回溯算法：求组合问题！

回溯算法大家是不是已经快忘了，还记得组合问题应该怎么求了么？哈哈哈

回溯算法其实就是暴力搜索，既然是暴力搜索为什么要非要用回溯呢？因为一些问题能暴力搜索出就不错了，找不出更好的办法。

给定两个整数 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(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}

组合问题Carl讲解视频如下：

对回溯算法已经记忆模糊的同学，可以看看文章看看模板看看视频再回忆一波。