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

发布时间:2024年01月09日

个人见解

感觉回溯算法其实和递归很像,也是用递归的做法,也有三部曲,但又不太一样的地方是递归中类似二叉树,只有纵向遍历(一层层往下遍历,没有横向遍历),而回溯算法中多的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;

? ? }

};

文章来源:https://blog.csdn.net/2301_80817427/article/details/135491673
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。