代码随想录day24 开启回溯算法

个人见解

感觉回溯算法其实和递归很像，也是用递归的做法，也有三部曲，但又不太一样的地方是递归中类似二叉树，只有纵向遍历（一层层往下遍历，没有横向遍历），而回溯算法中多的for循环就是横向遍历，说实话这一点我没有理解的太深，只是知道它类似于两个for循环中的第一个for循环，以后有更深的理解以后再来补全吧，先给出递归三部曲写法：
1、确定函数名和参数 void backTracking(参数)

2、确定终止条件，并在终止条件里存放结果和return

? ? ? ? if（终止条件）{

? ? ? ? ? ? ? ? 存放结果；

? ? ? ? ? ? ? ? return；

? ? ? ? }

3、确定单层递归逻辑

????????for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
? ? ? ? ????????处理节点;
? ? ? ? ????????backtracking(路径，选择列表); // 递归
? ? ? ????????? 回溯，撤销处理结果
? ? ????}

第77题. 组合

题目

给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。

示例: 输入: n = 4, k = 2 输出: [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]

思考

晕乎，虽说看了基础三部曲，但还是没啥头绪应该怎么写，卡在了终止条件上，看完卡哥的视频才恍然大悟，其实就是当临时vector存好元素后，将其放入res里，然后在单层递归的逻辑里迷糊于啥时候回溯pop_back()，应该是在终止条件return的时候

代码

class Solution {

public:

? ? vector<vector<int>> res;

? ? vector<int> path;

? ? void backTracking(int n, int k, int startIndex) {

? ? ? ? if(path.size() == k) {

? ? ? ? ? ? res.push_back(path);

? ? ? ? ? ? return;

? ? ? ? }

? ? ? ? for(int i = startIndex; i <= n; i++) {

? ? ? ? ? ? path.push_back(i);

? ? ? ? ? ? backTracking(n,k,i+1);

? ? ? ? ? ? path.pop_back();

? ? ? ? }

? ? }

? ? vector<vector<int>> combine(int n, int k) {

? ? ? ? backTracking(n,k,1);

? ? ? ? return res;

? ? }

};