DFS:深搜+回溯+剪枝解决组合问题

                                               创作不易,感谢支持!!!

一、电话号码的组合

. - 力扣(LeetCode)

class Solution {
public:string hash[10]={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};string path;//记录路径vector<string> ret;//记录返回值vector<string> letterCombinations(string digits) {if(digits.size()==0) return ret;dfs(digits,0);return ret;}void dfs(string &digits,int pos){if(path.size()==digits.size()) {ret.push_back(path);return;}for(auto ch:hash[digits[pos]-'0'])//从当前位置开始遍历,然后再去下一个里面找{path.push_back(ch);dfs(digits,pos+1);path.pop_back();}}
};

二、括号生成

. - 力扣(LeetCode)

class Solution {
public:vector<string> ret;string path;int n;vector<string> generateParenthesis(int _n) {n=_n;dfs(0,0);return ret;}void dfs(int open,int close)//open和close记录上界和下界{if(path.size()==2*n) {ret.push_back(path);return;}if(open<n) {path.push_back('(');dfs(open+1,close);path.pop_back();}if(close<open){path.push_back(')');dfs(open,close+1);path.pop_back();}}
};

 三、组合

. - 力扣(LeetCode)

class Solution {
public:vector<vector<int>> ret;vector<int> path;int k;//用k全局,可以减少一个参数int n;//用n全局,可以减少一个参数vector<vector<int>> combine(int _n, int _k) {k=_k;n=_n;dfs(1);return ret;}void dfs(int pos){if(path.size()==k) {ret.push_back(path);return;}for(int i=pos;i<=n;++i){path.push_back(i);dfs(i+1);path.pop_back();}}
};

四、目标和

. - 力扣(LeetCode)

class Solution {int ret=0;//记录返回结果
public:int findTargetSumWays(vector<int>& nums, int target) {dfs(nums,target,0,0);return ret;}void dfs(vector<int>& nums, int target,int index,int sum){if(index==nums.size()) {if(sum==target)  ++ret;}//选正数else{dfs(nums,target,index+1,sum+nums[index]);dfs(nums,target,index+1,sum-nums[index]);}}};

五、组合总和I

. - 力扣(LeetCode)

class Solution {vector<vector<int>> ret;vector<int> path;
public:vector<vector<int>> combinationSum(vector<int>& candidates, int target) {dfs(candidates,0,target);return ret;}void dfs(vector<int>& candidates,int pos,int target){if(target==0){ ret.push_back(path);return;}if(target<0) return;for(int i=pos;i<candidates.size();++i)//第一层,遍历每个数{path.push_back(candidates[i]);dfs(candidates,i,target-candidates[i]);//要从原先的位置去找path.pop_back();}}
};

class Solution {vector<vector<int>> ret;vector<int> path;
public:vector<vector<int>> combinationSum(vector<int>& candidates, int target) {dfs(candidates,0,target);return ret;}void dfs(vector<int>& nums,int pos,int target){if(target==0){ ret.push_back(path);return;}if(target<0||pos==nums.size()) return;for(int k=0;k*nums[pos]<=target;++k)//第一层,遍历每个数{if(k) path.push_back(nums[pos]);dfs(nums,pos+1,target-k*nums[pos]);//要从原先的位置去找}for(int k=1;k*nums[pos]<=target;++k) path.pop_back();//}
};

六、组合总和II

. - 力扣(LeetCode)

七、组合总和III

. - 力扣(LeetCode)

class Solution {
public:vector<vector<int>> ret;//记录组合vector<int> path;//记录路径vector<vector<int>> combinationSum3(int k, int n) { if(n>45) return ret;//剪枝dfs(k,n,1);return ret;}void dfs(int k,int n,int pos){if(k==0&&n==0) {ret.push_back(path);return;}if(n<0||k<0) return;for(int i=pos;i<=9;++i){path.push_back(i);dfs(k-1,n-i,i+1);path.pop_back();}}
};

八、组合总和IV

. - 力扣(LeetCode)

该题和前面是类似的,但是用回溯算法,会超时

class Solution {
public:int combinationSum4(vector<int>& nums, int target) {vector<int> dp(target + 1);dp[0] = 1;for (int i = 1; i <= target; i++) {for (int& num : nums) {if (num <= i&& dp[i - num] < INT_MAX - dp[i]) {dp[i] += dp[i - num];}}}return dp[target];}
};

 

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

MT3017 上色

思路&#xff1a;使用分治&#xff0c;在每个连续区域递归调用heng()和shu() #include <bits/stdc.h> using namespace std; int n, m; int h[5005];int shu(int l, int r) {return r - l 1; } int heng(int l, int r) {int hmin 0x3f3f3f3f;for (int i l; i < r;…

unity工程输出的log在哪里?

在编辑器里进行活动输出的log位置&#xff1a; C:\Users\username\AppData\Local\Unity\Editor\Editor.log ------------------------------------ 已经打包完成&#xff0c;形成的exe运行后的log位置&#xff1a; C:\Users\xxx用户\AppData\LocalLow\xx公司\xx项目

python相对路径导包与绝对路径导包的正确方式

【python相对路径导包与绝对路径导包的正确方式】 python相对路径导包与绝对路径导包的正确方式_哔哩哔哩_bilibilipython导包的难题&#xff0c;今天解决了&#xff0c;相对路径导包和绝对路径导包&#xff0c;均可以&#xff01;&#xff01;&#xff01;, 视频播放量 5、弹…

使用Coze工作流(二)

文章目录 使用Coze工作流 使用Coze工作流 通过本文你可以了解如何创建、发布、复制工作流&#xff0c;以及如何在 Bot 中添加工作流。 使用工作流的顺序如下&#xff1a; 创建工作流。 配置工作流。添加工作流节点并按照要处理的用户任务顺序连接工作流。 测试并发布工作流…

Java 面试宝典:请说下你对 Netty 中Reactor 模式的理解

大家好&#xff0c;我是大明哥&#xff0c;一个专注「死磕 Java」系列创作的硬核程序员。 本文已收录到我的技术网站&#xff1a;https://skjava.com。有全网最优质的系列文章、Java 全栈技术文档以及大厂完整面经 回答 Reactor 模式是一种高效处理并发网络事件的设计模式&…

大商创多用户商城系统 多处SQL注入漏洞复现

0x01 产品简介 大商创多用户商城系统是一个功能强大、灵活多变的新零售电商系统服务商。该系统支持平台自营和商家入驻,实现多元化经营模式,能够全面整合供应商、生产商、经销商和消费者等产业链资源,提高产品多样性,加快资金流动速度,并有助于减少不必要的成本输出。 0…

Python学习笔记-Flask接收post请求数据并存储数据库

1.引包 from flask import Flask, request, jsonify from flask_sqlalchemy import SQLAlchemy 2.配置连接,替换为自己的MySQL 数据库的实际用户名、密码和数据库名 app Flask(__name__) #创建应用实列 app.config[SQLALCHEMY_DATABASE_URI] mysqlpymysql://ro…

数据结构算法题(力扣)——链表

以下题目建议大家先自己动手练习&#xff0c;再看题解代码。这里只提供一种做法&#xff0c;可能不是最优解。 1. 移除链表元素&#xff08;OJ链接&#xff09; 题目描述&#xff1a;给一个链表的头节点 head 和一个整数 val &#xff0c;删除链表中所有满足值等于 val 的节点…

【Python系列】Python中的YAML数据读取与解析

&#x1f49d;&#x1f49d;&#x1f49d;欢迎来到我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐:kwan 的首页,持续学…

WebSocket用户验证

在WebSocket中&#xff0c;如何携带用户的验证信息 一、在OnMessage中进行验证 客户端在连接到服务器后&#xff0c;客户端通过发送消息&#xff0c;服务器端在OnMessage方法中&#xff0c;进行信息验证&#xff0c;这种方式需要将用户身份验证及接收用户消息进行混合处理&am…

Docker实战教程 第2章 Docker基础

3-1 Docker介绍 什么是Docker 虚拟化&#xff0c;容器 Docker 是一个开源的应用容器引擎&#xff0c;基于 Go 语言 并遵从Apache2.0协议开源。 Docker 可以让开发者打包他们的应用以及依赖包到一个轻量级、可移植的容器中&#xff0c;然后发布到任何流行的 Linux 机器上&…

VSCODE目录树缩进调整

VSCode默认的缩进太小了&#xff0c;简直看不出来&#xff0c;很容易弄混目录。在设置里修改就行了。 修改后效果&#xff1a;

Netty经典32连问

文章目录 1、Netty是什么&#xff0c;它的主要特点是什么&#xff1f;2、Netty 应用场景了解么&#xff1f;3、Netty 核心组件有哪些&#xff1f;分别有什么作用&#xff1f;4、Netty的线程模型是怎样的&#xff1f;如何优化性能&#xff1f;5、EventloopGroup了解么?和 Event…

基于springboot+vue实现的小区物业管理系统

作者主页&#xff1a;Java码库 主营内容&#xff1a;SpringBoot、Vue、SSM、HLMT、Jsp、PHP、Nodejs、Python、爬虫、数据可视化、小程序、安卓app等设计与开发。 收藏点赞不迷路 关注作者有好处 文末获取源码 技术选型 【后端】&#xff1a;Java 【框架】&#xff1a;spring…

蓝桥杯 - 受伤的皇后

解题思路&#xff1a; 递归 回溯&#xff08;n皇后问题的变种&#xff09; 在 N 皇后问题的解决方案中&#xff0c;我们是从棋盘的顶部向底部逐行放置皇后的&#xff0c;这意味着在任何给定时间&#xff0c;所有未来的行&#xff08;即当前行之下的所有行&#xff09;都还没…

如何在pgAdmin中用替换的值更新jsonb列?(二)

上一篇提到怎么替换jsonb&#xff0c;链接如下&#xff1a; 如何在pgAdmin中用替换的值更新jsonb列&#xff1f;-CSDN博客 那么当jsonb嵌套jsonb应该怎么替换呢&#xff1f;像这样&#xff0c;类型依然是jsonb&#xff0c;只不过嵌套一层&#xff0c;JsonData&#xff1a;&qu…

GDPU 竞赛技能实践 天码行空6

&#x1f4d6; 敌兵布阵 C国的死对头A国这段时间正在进行军事演习&#xff0c;所以C国间谍头子Derek和他手下Tidy又开始忙乎了。A国在海岸线沿直线布置了N个工兵营地,Derek和Tidy的任务就是要监视这些工兵营地的活动情况。由于采取了某种先进的监测手段&#xff0c;所以每个工…

统计子矩阵(前缀和+双指针)

题目描述 给定一个 N M 的矩阵 A&#xff0c;请你统计有多少个子矩阵 (最小 1 1&#xff0c;最大 N M) 满足子矩阵中所有数的和不超过给定的整数 K? 输入格式 第一行包含三个整数 N, M 和 K. 之后 N 行每行包含 M 个整数&#xff0c;代表矩阵 A. 输出格式 一个整数…

MySQL InnoDB引擎

InnoDB的逻辑存储结构如下图所示&#xff1a; 存储结构 表空间 表空间是InnoDB存储引擎逻辑结构的最高层&#xff0c; 如果用户启用了参数 innodb_file_per_table(在8.0版本中默认开启) &#xff0c;则每张表都会有一个表空间&#xff08;xxx.ibd&#xff09;&#xff0c;一个…

MySQL 索引底层探索:为什么是B+树?

MySQL 索引底层探索&#xff1a;为什么是B树&#xff1f; 1. 由一个例子总结索引的特点2. 基于哈希表实现的哈希索引3. 高效的查找方式&#xff1a;二分查找4. 基于二分查找思想的二叉查找树5. 升级版的BST树&#xff1a;AVL 树6. 更加符合磁盘特征的B树7. 不断优化的B树&#…