当前位置： 首页 > article >正文

【蓝桥杯速成】| 9.回溯升级

article 2025/3/22 8:59:16

题目一：组合综合

问题描述

39. 组合总和 - 力扣（LeetCode）

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。 

对于给定的输入，保证和为 target 的不同组合数少于 150 个。

示例 1：

输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。

解题步骤

这一题是在组合总和③上有了进一步的改进和要求

我们依旧可以用回溯三部曲模板解决

1.确定函数返回值及参数

这里我们需要从candidates数组中取值，所以这个数组应该一直陪伴我们，加入参数列表！

相当于我们之前从1~n中取值的n，都表示我们的取值范围

同理，我们需要一直参考target数值，所以它也是参数的一员

为了记录每个组合的总和，我们需要一个新变量用于存储，随之改变，所以加入新变量sum

最后仍然是我的开始索引，防止重复

void backtracking(vector<int>& candidates,int target,int sum,int startindex)

 2.确定终止条件

终止条件就是说我们找到答案会出现的情况，或者已知明确不可能出现答案就不要继续的情况

所以分开判断

if(sum>target){

        return;

}

if(sum==target){

        result.push_back(path);

        return;

}

3.单层搜索逻辑

使用for循环，遍历candidates数组中的每一个数字，

在每一层中我们需要往path中加入该数字

同时计算sum值

然后递归的使用backtracking函数，获得每一种可能情况

再进行回溯操作，sum值减去加入的数字值，数字也从path中pop_back

for(int i=startindex;i<candidates.size();i++){

        sum+=candidates[i];

        path.push_back(candidates[i]);

        backtracking(candidates,target,sum,startindex);//由于可以重复使用数字，所以此处startindex不需要+1

        sum-=candidates[i];

        path.pop_back();

}

最后只需要整合一下这个回溯函数，在主函数中正确传参调用即可！

完整代码如下！ 

code

class Solution {
public:
    vector<int> path;
    vector<vector<int>> result;
    void backtracking(vector<int>& candidates,int target,int sum,int startindex){
        if(sum>target){
            return;
        }
        if(sum==target){
            result.push_back(path);
            return;
        }
        for(int i=startindex;i<candidates.size();i++){
            sum+=candidates[i];
            path.push_back(candidates[i]);
            backtracking(candidates,target,sum,i);
            sum-=candidates[i];
            path.pop_back();
        }
    }
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        backtracking(candidates,target,0,0);
        return result;
    }
};

题目二：电话号码的字母组合

问题描述

17. 电话号码的字母组合 - 力扣（LeetCode）

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

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

示例 1：

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

示例 2：

输入：digits = ""
输出：[]

示例 3：

输入：digits = "2"
输出：["a","b","c"]

解题步骤

想必缩写对应数字这事大家肯定很熟悉了

（在背后说人家坏话或者讲机密时就用数字代号的事没少干ψ(｀∇´)ψ

那么这一题相较于之前的组合题区别就在于，它的选值对象不再是同一个范围内的数字了

而是存在数字对应字符串，在字符串中选取对应值，

并且这一题的组合长度也是固定的，给定dights有几位，我们的组合长度就是几位

简单分析就是这样，那当务之急就是解决数字对应字符串

这样才可以确定之后的取值范围

关于映射关系，我们可以选用数组和map

这里选择二维数组

const string lettermap[10]{

        "","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"

    };

 0号和1号位为空，虽然看似一维数组，但由于string可以按照数组使用，所以是二维滴！

同样，我们需要一个存储过程量和一个存储最后结果集的变量，

根据题目所求的数据类型，定义为👇

string s;//过程量，存储每一种可能

vector<string> result;//结果集，存放所有正确结果

ok，准备完毕，开始走回溯三部曲

1.确定函数返回值及参数

这里我们不能一味的拿来之前的参数列表使用，一定要明确参数的意义

当然返回值依然是void

要把数字转化为对应字母，那我们就需要该数字，和取到哪一位数字的一个标识

可以这么想，我们的函数需要递归调用的，每次都需要看取哪一位元素，

所以digits用来看，index用来指并且是要动态改变的

void backtracking(const string& digits,int index) 

 2.终止条件

既然我们已经派出index指向我们所挑选的数字

那么只要index的数值等于digits的大小，那就意味着指到最后一位了，完成我们的任务了！

所以满足终止条件，我们需要加入这个s到结果集中并返回

if(index==digits.size()){

        result.push_back(s);

        return;

}

 3.单层遍历逻辑

我们需要遍历的是当前数字所对应的字符串（或者说字符数组）

所以在执行遍历之前，我们应该取出这个字符数组

取出字符数组又分为两步

1).确认当前数字

2).找数字对应字符数组

int digit=digits[index]-'0';//digits为字符串类型，取出类型需要通过-'0'转为int型

string letters=lettermap[digit];//在我们的对应二维数组中找到对应string

 ok万事大吉，开始进入单层遍历逻辑

为方便理解我们用digits = "23"来举例，最开始肯定是拿到2对应的字符串“abc”嘛

那就遍历这个字符串for(int i=0;i<letters.size();i++)

在这个循环里，把单个字符串加入到s中，第一个加入的是"a"

然后递归调用backtracking函数，我们就可以拿到3对应的字符串“def”

然后再遍历“def”，分别与a进行组合，得到三个组合，a这个结点就组合完毕

最外层就可以再指向下一个b，再与def进行同样的组合

过程类似下图，只举例了第一个a的情况

 那么我们的单层遍历代码如下：

for(int i=0;i<letters.size();i++){

        s.push_back(letters[i]);

        backtracking(digits,index+1);

        s.pop_back();

}

整合所有代码， 在主函数中调用即可

这里呢我们可以做一个剪枝操作，

如果给我们的数字序列为空，那么直接返回result（初始为空）即可

if(digits.size()==0){

        return result;

}

code

class Solution {
public:
    string s;
    vector<string> result;
    const string lettermap[10]{
        "","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"
    };

    void backtracking(const string& digits,int index){
        if(index==digits.size()){
            result.push_back(s);
            return;
        }
        int dight=digits[index]-'0';
        string letters=lettermap[dight];
        for(int i=0;i<letters.size();i++){
            s.push_back(letters[i]);
            backtracking(digits,index+1);
            s.pop_back();
        }
    }
    vector<string> letterCombinations(string digits) {
        if(digits.size()==0){
            return result;
        }
        backtracking(digits,0);
        return result;
    }
};

补充：

const 是 constant 的缩写，本意是不变的，不易改变的意思。在 C++ 中是用来修饰内置类型变量，自定义对象，成员函数，返回值，函数参数。

C++ const 允许指定一个语义约束，编译器会强制实施这个约束，允许程序员告诉编译器某值是保持不变的。如果在编程中确实有某个值保持不变，就应该明确使用const，这样可以获得编译器的帮助。

题目三：组合总和②

问题描述

40. 组合总和 II - 力扣（LeetCode）

给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用 一次 。

注意：解集不能包含重复的组合。 

示例 1:

输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

示例 2:

输入: candidates = [2,5,2,1,2], target = 5,
输出:
[
[1,2,2],
[5]
]

解题步骤

不知道有没有和我一样的小蠢蛋，看到这一题没仔细审题还以为是之前做过没有提交

嘎嘎写完代码运行完才发现不对劲

这一题的特殊之处在于它所给的candidates是可能重复的，但最后要求解集中不能包含重复的

那么按照之前的逻辑，我们只能满足它在各不相同的情况下不重复，

但不能解决同一个取值空间中有相同元素的重复可能

所以这里我们要加入一个新的操作——去重

其它代码都大致相同就不多解释，重点来理一下去重的逻辑

我们需要在每一层去确认当前元素之前是否被使用过，

那么为了方便对比前后，可以先将整个candidates数组进行排序，

那相同值肯定就出现在旁边，不需要考虑是多久之前出现

sort(candidates.begin(), candidates.end());

同时需要留下记录，所以需要一个新的数组来存储这些记录

vector<bool> used(candidates.size(), false);//初始化为false全部没用过

那么这个used数组应该要伴随这组结果一直递归才能查看情况

所以把他加入参数列表

    void backtracking(vector<int>& candidates,int target,int sum,int index,vector<bool>& used){

那么在单层遍历中需要同时改变这个结点的使用状态

            sum+=candidates[i];

            path.push_back(candidates[i]);

            used[i]=true;

            backtracking(candidates,target,sum,i+1,used);

            used[i]=false;

            sum-=candidates[i];

            path.pop_back();

简单的已经铺垫完了，接下来捋一下去重方法

重复那就是candidates[i] == candidates[i - 1]，但是只加这一个条件会使我们失去确实用到两个相同元素的结果，而不是仅去掉重复的结果（细品这个差别）

所以还需要加上used[i - 1] == false代表对于同一树层candidates[i - 1]使用过（因为回溯所以false）

在满足这两个条件下我们就需要continue跳过这个组合结果

if (i > 0 && candidates[i] == candidates[i - 1] && used[i - 1] == false) {

                continue;

            }

完整代码如下！ 

code

class Solution {
public:
    vector<int> path;
    vector<vector<int>> result;
    int sum;
    void backtracking(vector<int>& candidates,int target,int sum,int index,vector<bool>& used){
        if(sum>target){
            return;
        }
        if(sum==target){
            result.push_back(path);
            return;
        }
        for(int i=index;i<candidates.size();i++){
            if (i > 0 && candidates[i] == candidates[i - 1] && used[i - 1] == false) {
                continue;
            }
            sum+=candidates[i];
            path.push_back(candidates[i]);
            used[i]=true;
            backtracking(candidates,target,sum,i+1,used);
            used[i]=false;
            sum-=candidates[i];
            path.pop_back();
        }
    }
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        vector<bool> used(candidates.size(), false);
        path.clear();
        result.clear();
        sort(candidates.begin(), candidates.end());
        backtracking(candidates,target,0,0,used);
        return result;
    }
};


http://www.kler.cn/a/595145.html

相关文章：

  • C/C++错误信息
  • 详细说明脚本评估和耗时较长的任务
  • mac上安装nvm及nvm的基本语法使用！！
  • 基于DeepSeek-R1 的RAG智能问答系统开发攻略
  • llama源码学习·model.py[3]ROPE旋转位置编码(4)ROPE的应用
  • 在linux服务器部署Heygem
  • 3月21号
  • 【设计模式】三十一、状态模式
  • [数据结构]排序之 归并排序（有详细的递归图解）
  • 微服务分层架构详解：表示层、应用层与基础设施层的协同工作
  • Python学习第二十二天
  • WPF UI元素保存为图像文件
  • L2和内积inner dot区别
  • Vue 3 自定义指令：实现自动滚动效果
  • 去中心化金融的风起与未来：从边缘创新到主流趋势
  • 4.1、网络安全模型
  • QT并发编程进阶--线程安全与同步技巧详解
  • Nexus L2 L3基本配置
  • VS010生成可由MATLAB2016调用的DLL文件方法
  • Sympy入门之微积分基本运算