首页 > 其他分享 >回溯初理解

回溯初理解

时间:2024-01-18 11:24:28浏览次数:24  
标签:return 递归 int 循环 理解 回溯 backtracking


首先要明确一点回溯也是纯暴力的一种方法,就是多层for循环。但是有的题目你不能写出它具体有多少层for循环,因此用递归来表示内侧for循环的逻辑。
比如说这道题,它for循环的数目是随着K变化的,K等于2是就两层for循环。
卡哥给出回溯算法框架

点击查看代码
void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

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

看这个框架,可以这样理解。for循环代表横向查找的过程,递归代表纵向查找的过程。
终止条件就是收获结果的过程。

该题因为不能插入同样的元素,因此下一层递归时就要跳过那个元素。
因此要在for循环中的起始条件改动,
for(int i=startflag;i<=n;i++),同时递归时startflag++就行。
如果要进行剪枝就要对for循环中的终止条件进行改动
for (int i = startIndex; i <= n - (k - path.size()) + 1; i++)

完整代码

点击查看代码
class Solution {
public:
vector<int>path;
vector<vector<int>>cnt;
void backtracking(int n,int k,int startflag){
    if(path.size()==k){
        cnt.push_back(path);
        return ;
    }
    for(int i=startflag;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 cnt;
    }
};

标签:return,递归,int,循环,理解,回溯,backtracking
From: https://www.cnblogs.com/yun-che/p/17972116

相关文章

  • 回溯 backtrack
    目录简介简介回溯算法是一种用于解决一些计算问题的通用算法,它会逐步构建候选解,并在确定候选解无法完成时放弃每个部分的候选解。回溯算法通常用于解决组合优化问题,如八皇后问题、0-1背包问题等。它使用递归的方式来尝试所有可能的解,并在搜索过程中进行剪枝,以提高效率。下面是......
  • Vuex的简单理解和使用
    1、什么是Vuex?在使用vue作为框架的前端项目开发中,我们经常会碰到Vuex,那么Vuex到底是什么东西呢?根据官方文档给出的解释是:Vuex是一个专为Vue.js应用程序开发的状态管理模式+库。它采用集中式存储管理应用的所有组件的状态,并以相应的规则保证状态以一种可预测的方式发生变化。简......
  • zabbix异常处理解决方案
                                    zabbix异常处理解决方案1、zabbix批量添加一百多台交换机导致,可以登录zabbix但是所有的监控值都无数据解决方案:       1》.查看zabbix-server.log   2......
  • 设备树 理解
    参考:https://doc.embedfire.com/linux/rk356x/driver/zh/latest/linux_driver/base_dynamic_device_tree.htmlhttps://www.jianshu.com/p/dc2919b140da:前的是节点别名;=前的是属性名;=后的是属性值;{前的是节点名;<>中既可以10进制数也可以16进制数初始......
  • 理解为什么用函数
    1.Shell函数是什么?shell函数开发:函数的特点,类似于alias别名一样,能够简化Linux命令的操作,让整个命令更易读,更易用1.函数,就是讲你需要执行的shell命令,组合起来,组合成一个函数体2.需要给函数体,起一个名字,这个名字就称之为函数名3.完整的就是函数名字+函......
  • 关于二叉树递归代码的粗鄙理解
    整体来看,二叉树的递归代码,可以分为终止条件,单层递归逻辑。单层递归逻辑就是所谓的根左右那三种,选哪一种也是有讲究的,如果不需要对根节点进行处理,那三种都可以。如果题目侧重与由子节点推到父节点,就采用后序遍历。如果题目侧重与由父节点推到子节点,就采用前序遍历。终止条件怎......
  • 回溯过程浅理解
    如何知道这一题需要用回溯呢?回溯就像试触,如果不符合条件,就往回缩,但是这种缩,不是回到起点,而是回到上一步。所以题目像二叉树路径,这样需要不断的试触并且要记录之前的路径信息的,就要用到回溯。关于回溯如何用,有一些关键点。有递归就有回溯,单层递归中有加就有减,(这个加减要广义......
  • 对进程以及创建进程的理解
    【一】进程和程序【1】什么是进程?进程就是正在运行的程序【2】谁来执行进程?cpu【3】进程和程序的区别?程序是存储再硬盘里面的一堆代码和数据进程是正在运行的程序【二】进程调度问题有一个算法叫做任务调度算法就像是一个非常聪明的调度员,在计算机系统中负责安排......
  • javascript node.js , java jvm , jdk, jre 的理解。
    网上的截图: 来看看node.js     再来看看java.     ......
  • 正确理解c# default关键字
    背景最近QA测试一个我开发的一个WebAPI时,我意识到之前对C#的default的理解一直是想当然的。具体情况是这样,这个API在某些条件下要返回模型的默认值,写法类似于下面这样[HttpGet(Name="GetWeatherForecast")]publicWeatherForecastGet(){returndefault;}实际上,这个......