Leetcode

回溯算法中递归的逻辑不重要只要掌握回溯的模板以及将问题转化为树形图整个问题就很好解决了比二叉树简单。

Leetcode

思路套回溯的模板终止条件是pathk。

然后将题目描述的组合逻辑想象成树形结构

class

index){if(path.size()k)//终止条件{res.push_back(path);return;}for(int

iindex;in;i)树形结构逻辑{path.push_back(i);backtracking(n,

i1);path.pop_back();回溯}return;}vectorvectorint

combine(int

思路这个题和上一道题唯一的区别就是终止条件加了一个和等于目标值树形结构基本没变

class

index){if(sumnpath.size()k)//终止条件{res.push_back(path);return;}for(int

iindex;i9;i)树形结构逻辑{path.push_back(i);sumi;backtracking(k,

i1);sum-i;//回溯path.pop_back();}return;}

vectorvectorint

思路这道题目的终止条件和上面三道题几乎一样只不过树形逻辑要通过一个二维字符串数组做一个映射。

class

index){if(path.size()a.size())//终止条件{res.push_back(path);return;}int

i0;iletter.size();i)//树形结构逻辑{path.push_back(letter[i]);backtracking(a,

index1);path.pop_back();//回溯}return;}vectorstring

digits)

求解回溯模板需要想好终止条件以及树形逻辑的代码编写不需要仔细思考递归逻辑相比于二叉树的各种遍历简单许多。