回溯算法—组合问题

文章目录

  • 介绍
  • 应用问题
  • 基本流程
  • 算法模版
  • 例题
    • (1)组合
    • (2)电话号码的字母组合

介绍

回溯算法实际上是 一个类似枚举的搜索尝试过程,主要是在搜索尝试过程中寻找问题的解,当发现已不满足求解条件时,就“回溯”返回,尝试别的路径。

应用问题

  • 组合问题:N个数里面按一定规则找出k个数的集合
  • 子集问题:一个N个数的集合里有多少符合条件的子集
  • 切割问题:一个字符串按一定规则有几种切割方式
  • 排列问题:N个数按一定规则全排列,有几种排列方式
  • 棋盘问题:N皇后,解数独等等

基本流程

  • 选择:在当前步骤中,从可选的选择中选择一个。
  • 验证:检查选择是否满足问题的约束条件和限制。
  • 递归:进入下一步骤,继续选择和验证。
  • 撤销:如果选择不满足问题要求,回溯到上一步,撤销当前选择,并尝试其他选择。

回溯法解决的问题都可以抽象为树形结构

集合的大小就构成了树的宽度,递归的深度就构成了树的深度

算法模版

void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

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

递归嵌套for循环

回溯三部曲:

  1. 递归函数的参数和返回值:返回值一般为void
  2. 确定终止条件
  3. 单层搜索的逻辑

例题

(1)组合

77. 组合 - 力扣(LeetCode)

给定两个整数 nk,返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按 任何顺序 返回答案。

示例 1:

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

组合是无序的,[1,2]和[2,1]一致

每一个节点都是一层for循环,从startIndex开始

tree
  1. 递归函数的参数和返回值:

    void backTracking(int n, int k, int startIndex)
    
  2. 确定终止条件

    到达叶子节点,path数组大小到达k

    if (pathtop == k) 
    
  3. 单层搜索的逻辑

    for循环从startIndexn中选择数字(startIndex控制每次搜索时的起始位置,本题第一次调用时传1

    先处理当前i节点;
    再递归:传入i+1控制下一层递归起始位置;
    回溯:退出递归调用之后,需要回溯到之前的状态,来尝试其他数字并构建其他组合。因此 pathtop 减 1,i + 1退出递归后在当前循环还是i

    for (int i = startIndex; i <= n; i++) {
            path[pathtop++] = i; // 存入结果
            backTracking(n, k, i + 1); // 递归,传入i+1,下一层递归起始位置
            pathtop--;
    }
    

    for循环横向遍历,递归纵向遍历,回溯不断调整结果集

int* path;
int pathtop;
int** ret;
int rettop;
void backTracking(int n, int k, int startIndex) {
    if (pathtop == k) {
        int* temp = (int*)malloc(sizeof(int) * k);
        for (int i = 0; i < k; i++) {
            temp[i] = path[i];
        }
        ret[rettop++] = temp;
        return;
    }
    for (int i = startIndex; i <= n; i++) {
        path[pathtop++] = i;
        backTracking(n, k, i + 1);
        pathtop--;
    }
}
int** combine(int n, int k, int* returnSize, int** returnColumnSizes) {
    pathtop = 0;
    rettop = 0;
    path = (int*)malloc(sizeof(int) * k);
    ret = (int**)malloc(sizeof(int*) * 1000000);
    backTracking(n, k, 1);
    
    *returnSize = rettop;
    (*returnColumnSizes) = (int*)malloc(sizeof(int) * (*returnSize));
    for (int i = 0; i < (*returnSize); i++) {
        (*returnColumnSizes)[i] = k;
    }
    return ret;
}

剪枝

时间复杂度:叶子个数乘叶子到根的路径长度

for循环在寻找起点的时候要有一个范围,如果这个起点到集合终止之间的元素已经不够题目要求的k个元素了,就没有必要搜索了

例如如果n = 4, k = 4情况下

nk4

已经选择的数量:pathTop

还需要选择的数量:k - pathTop

集合n中至多要从n - (k - pathTop) + 1 开始遍历

[1,2,3,4]

n=4,k=3,假设选了一个了,还要选两个,那么至多从n - 2 + 1 = 3

假设选了0个,那么还要选三个,那么至多从n - 3 + 1 = 2

 for (int i = startIndex; i <= (n - k + pathtop + 1); i++) {
        path[pathtop++] = i;
        backTracking(n, k, i + 1);
        pathtop--;
 }

(2)电话号码的字母组合

17. 电话号码的字母组合 - 力扣(LeetCode)

给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。

示例 1:

输入:digits = "23"
输出:["ad","ae","af","bd","be","bf","cd","ce","cf"]

示例 2:

输入:digits = ""
输出:[]
  1. 递归函数的参数和返回值:

    void backTracking(char* digits, int length, int index)
    
  2. 确定终止条件

    遍历到字符串末尾

     if (pathTop == length) 
    
  3. 单层搜索的逻辑

    创建一个map[10][5] 来存储不同号码对应的字母

    for循环遍历的是map[i] 的长度
    在这里插入图片描述

char** ret;
int retTop;
char* path;
int pathTop;
char map[10][5] = {"\0",    "\0",    "abc\0",  "def\0", "ghi\0",
                   "jkl\0", "mno\0", "pqrs\0", "tuv\0", "wxyz\0"};
void backTracking(char* digits, int length, int index) {
    // 当遍历到字符串末尾时,将当前组合加入结果集中
    if (index == length) {
        char* temp = (char*)malloc(sizeof(char) * (pathTop + 1));
        memcpy(temp, path, sizeof(char) * pathTop);
        temp[pathTop] = '\0';
        ret[retTop++] = temp; 
        return;
    }
    // 获取当前数字对应的字符集合的长度
    int num = digits[index] - '0';
    int letterLength = strlen(map[num]);
    // 遍历当前数字对应的字符集合
    for (int i = 0; i < letterLength; i++) {
        // 当前组合长度达到字符串长度时,退出循环
        if (pathTop >= length) {
            break;
        }
        // 将当前字符加入当前组合中
        path[pathTop++] = map[num][i];
        backTracking(digits, length, index + 1);
        pathTop--;
    }
}

// 主函数,生成数字键盘对应的所有字母组合
char** letterCombinations(char* digits, int* returnSize) {
    retTop = pathTop = 0;
    int maxPathLength = strlen(digits) * 4; 
    
    path = (char*)malloc(sizeof(char) * (maxPathLength + 1));
    ret = (char**)malloc(sizeof(char*) * 1000);
    
    // 初始化结果集数组为空
    for (int i = 0; i < 1000; ++i) {
        ret[i] = NULL;
    }
    int length = strlen(digits);
    
    // 输入字符串长度为0返回空结果集
    if (length == 0) {
        *returnSize = 0;
        return ret;
    }
    
    backTracking(digits, length, 0);
    
    *returnSize = retTop; 
    return ret; 
}

参考:

  1. 代码随想录 (programmercarl.com)
  2. 回溯算法套路②组合型回溯+剪枝
  3. 17. 电话号码的字母组合 - 力扣(LeetCode)


如有错误烦请指正。

感谢您的阅读

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/611427.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

CSS-页面导航栏实现-每文一言(过有意义的生活,做最好的自己)

&#x1f390;每文一言 过有意义的生活,做最好的自己 目录 &#x1f390;每文一言 &#x1f6d2;盒子模型 &#x1f453;外间距 (margin) &#x1f97c;边框 &#x1f45c;内边距 切换盒子模型计算方案&#xff1a; &#x1f3a2; 浮动布局 浮动特点 &#x1f3c6;导航…

并行执行的4种类别——《OceanBase 并行执行》系列 4

OceanBase 支持多种类型语句的并行执行。在本篇博客中&#xff0c;我们将根据并行执行的不同类别&#xff0c;分别详细阐述&#xff1a;并行查询、并行数据操作语言&#xff08;DML&#xff09;、并行数据定义语言&#xff08;DDL&#xff09;以及并行 LOAD DATA 。 《并行执行…

Docker部署Metabase

文章目录 Docker安装MetabaseCentOS7安装Docker获取最新的 Docker 镜像启动Metabase容器在Metabase初始化时查看日志访问Metabase Metabase 的 ClickHouse 驱动程序安装环境简介删除容器创建容器下载click house驱动放入驱动重启容器将元数据库连接到 ClickHouse报错解决 Docke…

轻松管理文件夹批量重命名:学会用关键词批量替换文件夹名称技巧

随着计算机中存储的文件和文件夹数量不断增加&#xff0c;如何有效地管理和组织它们变得尤为重要。批量重命名文件夹是提升文件管理效率的关键步骤之一。而利用云炫文件管理器中关键词批量替换文件夹名称的技巧&#xff0c;则可以帮助我们更快速地完成这一任务。 关键词批量替…

LeetCode例题讲解:876.链表的中间结点

给你单链表的头结点 head &#xff0c;请你找出并返回链表的中间结点。 如果有两个中间结点&#xff0c;则返回第二个中间结点。 示例 1&#xff1a; 输入&#xff1a;head [1,2,3,4,5] 输出&#xff1a;[3,4,5] 解释&#xff1a;链表只有一个中间结点&#xff0c;值为 3 。…

KMeans,KNN,Mean-shift算法的学习

1.KMeans算法是什么&#xff1f; 在没有标准标签的情况下&#xff0c;以空间的k个节点为中心进行聚类&#xff0c;对最靠近他们的对象进行归类。 2.KMeans公式&#xff1a; 2. 1.关键分为三个部分&#xff1a; 1.一开始会定义n个中心点&#xff0c;然后计算各数据点与中心点…

浅谈云计算资源和服务

目录 前言 正文 专有名词及其首字母缩写 轻量级应用服务器 云服务器ECS 专有网络VPC 其他类服务 尾声 &#x1f52d; Hi,I’m Pleasure1234&#x1f331; I’m currently learning Vue.js,SpringBoot,Computer Security and so on.&#x1f46f; I’m studying in University o…

如何用Python创建目录以及自动创建缺失的父目录

在Python中&#xff0c;创建目录&#xff08;也称为文件夹&#xff09;是一个常见的任务&#xff0c;尤其是当你需要为文件系统上的某些文件创建存储位置时。幸运的是&#xff0c;Python的os模块提供了一个非常方便的函数os.makedirs()&#xff0c;它允许你创建一个目录&#x…

【AMBA Bus ACE 总线 8 -- ICache maintenance】

请阅读【AMBA Bus ACE 总线与Cache 专栏 】 欢迎学习:【嵌入式开发学习必备专栏】 文章目录 ACE ICache maintenanceACE ICache maintenance 图 1-1 当一个OS run 多个cpu的时候,根据调度算法的不同,OS 可以根据调度算法的不同分别 run 在某个具体的CPU上,因此,它们会有…

计算图与自动微分

计算图与自动微分 一、自动梯度计算1.1 数值微分&#xff08;Numerical Differentiation&#xff09;1.2 符号微分&#xff08;Symbolic Differentiation&#xff09;1.3 自动微分&#xff08;Automatic Differentiation&#xff0c;AD&#xff09;1.3.1 计算图1.3.2 正向传播1…

java技术总结

1.java基本数据类型? byte 1,short 2 ,int 4,long 8 ,float 4,double 8,boolean 1,char 2 2.java为什么要有包装类型? 前 6 个类派生于公共的超类 Number,而 Character 和 Boolean 是 Object 的直接子类。 被 final 修饰, Java 内置的包装类是无法被继承的。 包装…

FreeRTOS标准库例程代码

1.设备STM32F103C8T6 2.工程模板 单片机: 部分单片机的程序例程 - Gitee.comhttps://gitee.com/lovefoolnotme/singlechip/tree/master/STM32_FREERTOS/1.%E5%B7%A5%E7%A8%8B%E6%A8%A1%E6%9D%BF 3.代码 1-FreeRTOS移植模板 #include "system.h" #include "…

腾讯云coding代码托管平台配置问题公钥拉取失败提示 Permission denied(publickey)

前言 最近在学校有个课设多人开发一个游戏&#xff0c;要团队协作&#xff0c;选用了腾讯云的coding作为代码管理仓库&#xff0c;但在配置的时候遇到了一些问题&#xff0c;相比于github&#xff0c;发现腾讯的coding更难用&#xff0c;&#xff0c;&#xff0c;这里记录一下…

【进程替换】进程程序替换函数execl | 单进程程序替换原理

目录 直接看现象&#xff08;单进程&#xff09; 单进程程序替换原理 替换函数 直接看现象&#xff08;单进程&#xff09; 我们先使用execl来直接看现象man 3 execlexecute a file执行一个程序int execl(const char *path, const char *arg, ...);execl函数的返回值&#x…

使用GitLab自带的CI/CD功能在K8S集群里部署项目(四)

前置内容&#xff1a; 通过Docker Compose部署GitLab和GitLab Runner&#xff08;一&#xff09; 使用GitLab自带的CI/CD功能在本地部署项目&#xff08;二&#xff09; 使用GitLab自带的CI/CD功能在远程服务器部署项目&#xff08;三&#xff09; 一、K8S集群信息 节点名称…

Unity TileMap入门

概述 相信很多同学学习制作游戏都是从2D游戏开始制作的吧&#xff0c;瓦片地图相信大家都有接触&#xff0c;那接下来让我们学习一下这部分的内容吧&#xff01; Tilemap AnimationFrameRate:设置每帧动画的播放速率。Color:瓦片地图的颜色TileAnchor:锚点&#xff0c;&#x…

笔试强训week4

day1 Q1 难度⭐⭐ 小易的升级之路_牛客题霸_牛客网 (nowcoder.com) 题目&#xff1a; 小易经常沉迷于网络游戏.有一次,他在玩一个打怪升级的游戏,他的角色的初始能力值为 a.在接下来的一段时间内,他将会依次遇见n个怪物,每个怪物的防御力为b1,b2,b3...bn. 如果遇到的怪物防…

马斯克:脑机接口迎来首例植入者,芯片接线发生故障。

马斯克旗下的脑机接口公司Neuralink近日传出关于首例植入者诺兰阿博脑机接口芯片故障的消息。根据Neuralink发布的文章&#xff0c;诺兰阿博的脑机设备发生了故障&#xff0c;多根植入他大脑的接线已经脱落&#xff0c;导致获取数据量减少。目前该公司正在研究导致接线脱落的原…

Java进阶08 集合(续)Stream流

Java进阶08 集合&#xff08;续&#xff09;&Stream流 一、HashSet集合类&#xff08;续&#xff09; 1、JDK7(-)HashSet原理解析 1.1 底层结构 数组链表 1.2 执行过程 ①创建一个默认长度为16的数组&#xff0c;数组名为table ②根据元素的哈希值跟数组的长度求余计…

灰狼优化算法(Grey Wolf Optimizer)

注意&#xff1a;本文引用自专业人工智能社区Venus AI 更多AI知识请参考原站 &#xff08;[www.aideeplearning.cn]&#xff09; 算法引言 灰狼算法&#xff08;Grey Wolf Optimizer, GWO&#xff09;是一种受自然界灰狼行为启发的优化算法。它模拟了灰狼的社会层次和狩猎策…