C++算法练习-day52——216.组合总和3

news/2024/12/2 4:38:57/

题目来源:. - 力扣(LeetCode)

题目思路分析

题目描述
combinationSum3 问题要求从 1 到 9 的整数中找出所有可能的 k 个数的组合,使得这些数的和等于给定的整数 n。注意,这里的每个数字只能使用一次,且组合中的数字需要是唯一的。

解题思路

  1. 回溯算法:这是一个典型的回溯问题,我们需要尝试所有可能的组合,并在每一步中检查是否满足条件(组合的长度为 k 且和为 n)。
  2. 递归调用:通过递归调用,我们可以逐步构建当前的组合,并在每一步中决定是否继续添加下一个数字。
  3. 剪枝:如果当前组合的长度已经达到 k 或当前和已经小于 n(因为我们是从大到小遍历数字,所以一旦和小于 n,后续无论如何都无法使和等于 n),我们可以提前终止当前分支的搜索。
  4. 逆序遍历:由于我们需要从 1 到 9 中选择数字,且每个数字只能使用一次,因此我们可以选择逆序遍历这些数字。这样做的好处是,在回溯过程中,我们可以更容易地剪枝,因为一旦当前和小于 n,后续的数字(由于它们是更小的数字)也无法使和达到 n。

代码:

#include <vector>  class Solution {  
public:  // 回溯函数  void Backtracking(vector<vector<int>>& ans, // 存储所有有效组合的二维向量  vector<int>& sum,         // 当前正在构建的组合  int k, int n,             // 目标组合的长度和目标总和  int index) {              // 当前尝试的数字(从大到小遍历)  // 如果当前组合长度等于k且总和等于n,则找到一个有效组合  if (sum.size() == k && n == 0) {  ans.push_back(sum);  return;  }  // 如果组合长度达到k或总和已经小于n,则无需继续探索  if (sum.size() == k || n < 0) {  return;  }  // 逆序遍历从 index 到 1 的所有数字(注意这里 index 初始化为 10,是为了方便从 9 开始遍历)  for (index -= 1; index >= 1; --index) {  n -= index;        // 将当前数字从目标和中减去  sum.push_back(index); // 将当前数字加到当前组合中  Backtracking(ans, sum, k, n, index); // 递归调用,但注意 index 不再变化,因为我们是在遍历  n += index;        // 回溯:将当前数字加回到目标和中  sum.pop_back();    // 回溯:从当前组合中移除当前数字  }  }  // 主函数  vector<vector<int>> combinationSum3(int k, int n) {  vector<vector<int>> ans; // 存储所有有效组合的二维向量  vector<int> sum;         // 当前正在构建的组合  Backtracking(ans, sum, k, n, 10); // 从 10 开始(实际上从 9 开始遍历,因为 index-=1)  return ans;  }  
};

注释详解

  • Backtracking 函数是回溯算法的核心,它尝试构建所有可能的组合。
  • ans 存储所有有效的组合。
  • sum 存储当前正在构建的组合。
  • k 和 n 分别是目标组合的长度和目标总和。
  • index 是当前尝试的数字(从大到小遍历)。
  • 在 Backtracking 函数中,我们首先检查是否找到了一个有效的组合(长度等于 k 且和为 n)。
  • 然后,我们检查是否需要剪枝(组合长度达到 k 或和小于 n)。
  • 接下来,我们逆序遍历从 index 到 1 的所有数字,并递归调用 Backtracking 函数。
  • 在回溯过程中,我们更新目标和与当前组合,并在递归调用后恢复它们的状态。

知识点摘要

  • 回溯算法:一种通过构建候选解并逐步扩展直到满足问题要求或无法再扩展的算法。
  • 递归调用:函数直接或间接调用自身,用于在回溯算法中逐步构建候选解。
  • 剪枝:在搜索过程中提前终止不符合要求的候选解,以减少不必要的计算。
  • 逆序遍历:在处理类似问题时,逆序遍历可以更方便地进行剪枝。

combinationSum3 问题是一个典型的回溯算法问题,通过递归调用和剪枝来找出所有满足条件的组合。在回溯过程中,我们逐步构建当前组合,并在每一步中检查是否满足条件。如果不满足条件,则回溯并尝试其他可能的数字。逆序遍历数字可以更方便地进行剪枝,从而提高算法的效率。通过理解回溯算法的基本原理和递归调用的方式,我们可以更好地解决类似的问题。


http://www.ppmy.cn/news/1551665.html

相关文章

将jar包导入maven

1.将jar包放repository 2.执行命令&#xff1a;mvn install:install-file -DgroupIdcom.oracle -DartifactIdojdbc7 -Dversion12.1.0.2 -Dpackagingjar -DfileD:\dev\utils\idea\repository\ojdbc7.jar -Dfile: 指定要安装的JAR文件的路径。 -DgroupId: 指定项目的groupId。 -…

Mybatis:CRUD数据操作之多条件查询及动态SQL

Mybatis基础环境准备请看&#xff1a;Mybatis基础环境准备 本篇讲解Mybati数据CRUD数据操作之多条件查询 1&#xff0c;编写接口方法 在 com.itheima.mapper 包写创建名为 BrandMapper 的接口。在 BrandMapper 接口中定义多条件查询的方法。 而该功能有三个参数&#xff0c;…

量化交易系统开发-实时行情自动化交易-8.4.MT4/MT5平台

19年创业做过一年的量化交易但没有成功&#xff0c;作为交易系统的开发人员积累了一些经验&#xff0c;最近想重新研究交易系统&#xff0c;一边整理一边写出来一些思考供大家参考&#xff0c;也希望跟做量化的朋友有更多的交流和合作。 接下来会对于MT4/MT5平台介绍。 MetaT…

龙迅#LT8612UX适用于HDMI 转 HDMIVGA应用领域,分辨率高达4K60HZ,内置程序,方便调试!

1. 描述 LT8612UX 是一款 HDMI 转 HDMI&VGA 转换器&#xff0c;可将 HDMI2.0 数据流转换为 HDMI2.0 信号和模拟 RGB 信号。它还输出 8 通道 I2S 和 SPDIF 信号&#xff0c;可实现高质量的 7.1 通道音频。 LT8612UX 使用最新的 ClearEdge 技术&#xff0c;除了原始的 HDMI…

关于按天切割Tomcat的catalina.out日志文件的配置

1、catalina.out 是 Tomcat 的标准输出和标准错误日志&#xff0c;通常输出到 Tomcat 安装目录下的 logs 文件夹中。这个日志文件会记录 Tomcat 启动、停止以及运行过程中产生的所有日志信息。 2、在Apache Tomcat中&#xff0c;日志文件catalina.out默认情况下不会自动按天切割…

深入学习指针(5)!!!!!!!!!!!!!!!

文章目录 1.回调函数是什么&#xff1f;2.qsort使用举例2.1使用qsort函数排序整形数据2.2使用sqort排序结构数据 3.qsort函数的模拟实现 1.回调函数是什么&#xff1f; 回调函数就是⼀个通过函数指针调⽤的函数。 如果你把函数的指针&#xff08;地址&#xff09;作为参数传递…

【商业化GPT】AI对话|绘画|音乐|视频|文件|知识库于一体的商业化GPT解决方案

急速AI 是一个综合性的 AI Web 应用平台&#xff0c;旨在为用户提供一个集成化、易于部署的人工智能服务站点。参考ChatGPT 官网的理念&#xff0c;将多种 AI 技术集成于一个单一的平台中&#xff0c;从而提供了一个全方位的 AI 服务体验&#xff0c;包括但不限于对话、绘画、语…

LabVIEW实现UDP通信

目录 1、UDP通信原理 2、硬件环境部署 3、云端环境部署 4、UDP通信函数 5、程序架构 6、前面板设计 7、程序框图设计 8、测试验证 本专栏以LabVIEW为开发平台,讲解物联网通信组网原理与开发方法,覆盖RS232、TCP、MQTT、蓝牙、Wi-Fi、NB-IoT等协议。 结合实际案例,展示如何利…