回溯算法大家是不是都快忘记了，还记得组合题是怎么解的吗？哈哈哈回溯算法其实就是暴力搜索。既然是暴力搜索，为什么还要用回溯呢？因为有些问题可以暴力搜索很好，我找不到更好的方法。给定两个整数n和k，返回1...n中k个数字的所有可能组合。如果用for循环逐层嵌套来解决这个问题，如果n为100，k为50，那么for循环就有50层。这时候，你会发现单纯的暴力是不够的。回溯算法开始发挥作用。在回溯算法中，使用递归来做for循环的堆叠和嵌套（可以理解为开k层for循环）。每个递归嵌套一个for循环，那么递归就可以解决多层嵌套循环的问题。在我的文章BacktrackingAlgorithm:FindingCombinationProblems!中，我也给出了回溯三部曲。按照这个方法，发现回溯算法其实并不难。题目链接：https://leetcode-cn.com/problems/combinations/回溯算法模板如下：voidbacktracking(parameter){if(terminationcondition){storeresult;return;}for(selection:elementsinthecollectionofthislayer(tree中间节点孩子的数量是集合的大小)){processingnode;backtracking(path,selectionlist);//递归回溯，撤销处理结果}}二维码关注。转载本文请联系CodeCaprice公众号。
