6
回溯算法：求组合问题！
source link: http://developer.51cto.com/art/202101/643764.htm
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
回溯算法大家是不是已经快忘了，还记得组合问题应该怎么求了么?哈哈哈
回溯算法其实就是暴力搜索，既然是暴力搜索为什么要非要用回溯呢?因为一些问题能暴力搜索出就不错了，找不出更好的办法。
给定两个整数 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(路径，选择列表); // 递归
回溯，撤销处理结果
}
}
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK