刷题笔记Day22回溯算法part01

刷题笔记Day22：回溯算法part01

回溯算法在之前递归中就有涉及，例如之前的所有可能路径的题目就用到了回溯的思想
回溯出现的位置都是在递归之后，且回溯就是纯的暴力算法。（解决for循环无法暴力破解的方法）
回溯所要解决的问题

• 组合问题
  
• 切割问题
  
• 子集问题
  
• 排列问题
  
• 棋盘问题
  

回溯问题都可以看成是一个N叉树的问题，下面引用一张代码随想录中的图片便于理解

回溯算法模板框架：

1. void backtracking(参数) {
2.     if (终止条件) {
3.         存放结果;
4.         return;
5.     }
7.     for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
8.         处理节点;
9.         backtracking(路径，选择列表); // 递归
10.         回溯，撤销处理结果
11.     }
12. }

复制代码

题目：77. 组合

组合
给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。
思路:可以将整个过程转化为N叉树的模式，横向即为for循环为纵向即为递归逻辑，而终止条件即为我们需要多少层的for循环，在本题中为k个for循环。

代码：如下：
[code]class Solution {public:    vector result;    vectortmp;    void backtracking(int start, int end,int k){        if(k == 0){            result.push_back(tmp);            return;        }        for(int i = start;i