代码随想录算法训练营第二十三天| 39. 组合总和

2024-08-23 03:52

本文主要是介绍代码随想录算法训练营第二十三天| 39. 组合总和,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

39. 组合总和

题目:

给你一个 无重复元素 的整数数组 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 。
仅有这两种组合。

示例 2:

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

示例 3:

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

提示:

  • 1 <= candidates.length <= 30
  • 2 <= candidates[i] <= 40
  • candidates 的所有元素 互不相同
  • 1 <= target <= 40

思路:

回溯思路

  1. 初始化结果列表:我们需要一个列表来存储所有的组合结果。

  2. 排序候选数组:虽然题目中没有要求,但对候选数组进行排序可能会有助于优化算法,比如在递归中可以提前停止搜索。

  3. 定义递归函数递归终止条件

      • 如果 target == 0,说明找到了一个符合条件的组合,将其添加到结果列表中。
      • 如果 target < 0,则当前组合不满足条件,直接返回。
    • 递归过程
      • 遍历候选数组,从start_index开始,每个数字都可以多次选取。
      • 将当前候选数字添加到组合中,更新目标值为 target - candidates[i]
      • 递归调用函数继续寻找组合。
      • 回溯:移除组合中的最后一个数字,尝试下一个候选数字。

上代码:

class Solution {
public:vector<vector<int>> combinationSum(vector<int>& candidates, int target) {vector<vector<int>> result;   // 存储所有符合条件的组合vector<int> current_combination;  // 当前组合// 调用递归函数开始回溯backtrack(candidates, target, current_combination, result, 0);return result;}private:void backtrack(vector<int>& candidates, int target, vector<int>& current_combination, vector<vector<int>>& result, int start_index) {if (target == 0) {// 找到一个符合条件的组合,将其添加到结果中result.push_back(current_combination);return;}if (target < 0) {// 当前组合不满足条件,返回return;}for (int i = start_index; i < candidates.size(); ++i) {// 选择当前候选数字current_combination.push_back(candidates[i]);// 递归调用继续搜索,target 减去当前候选数字,start_index 保持不变以允许重复选取backtrack(candidates, target - candidates[i], current_combination, result, i);// 回溯:移除当前组合中的最后一个数字current_combination.pop_back();}}
};

40.组合总和II

题目:

给定一个候选人编号的集合 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]
]

提示:

  • 1 <= candidates.length <= 100
  • 1 <= candidates[i] <= 50
  • 1 <= target <= 30

思路:

这个问题和之前的问题类似,只不过这次每个数字在组合中只能使用一次,并且不能包含重复的组合。为了实现这一点,我们需要稍微修改一下回溯算法。

主要思路
  1. 排序候选数组:首先对 candidates 进行排序,这样可以方便地跳过重复的元素,避免生成重复的组合。

  2. 定义递归函数递归终止条件

      • 如果 target == 0,表示找到一个符合条件的组合,将其加入到结果列表中。
      • 如果 target < 0,则当前组合不满足条件,直接返回。
    • 递归过程
      • start_index 开始遍历候选数组,每次选取一个数字加入组合。
      • 为了避免重复组合,在遍历过程中,如果发现当前数字和前一个数字相同,则跳过当前数字(即 candidates[i] == candidates[i-1])。
      • 递归调用时,将目标值减去当前选中的数字,并将 start_index 设置为 i+1,表示下一个候选数字只能从当前数字的后面开始选取。
      • 回溯:从组合中移除最后一个数字,继续尝试下一个候选数字

上代码:

class Solution {
public:vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {vector<vector<int>> result;   // 存储所有符合条件的组合vector<int> current_combination;  // 当前组合sort(candidates.begin(), candidates.end());  // 对候选数组进行排序// 调用递归函数开始回溯backtrack(candidates, target, current_combination, result, 0);return result;}private:void backtrack(vector<int>& candidates, int target, vector<int>& current_combination, vector<vector<int>>& result, int start_index) {if (target == 0) {// 找到一个符合条件的组合,将其添加到结果中result.push_back(current_combination);return;}for (int i = start_index; i < candidates.size(); ++i) {// 跳过重复的元素if (i > start_index && candidates[i] == candidates[i - 1]) continue;// 如果当前数字大于目标值,直接跳过后续的循环if (candidates[i] > target) break;// 选择当前候选数字current_combination.push_back(candidates[i]);// 递归调用继续搜索,target 减去当前候选数字,start_index + 1 保证每个数字只能使用一次backtrack(candidates, target - candidates[i], current_combination, result, i + 1);// 回溯:移除当前组合中的最后一个数字current_combination.pop_back();}}
};

131.分割回文串

题目:

给你一个字符串 s,请你将 s 分割成一些子串,使每个子串都是 

回文串

 。返回  s 所有可能的分割方案。

示例 1:

输入:s = "aab"
输出:[["a","a","b"],["aa","b"]]

示例 2:

输入:s = "a"
输出:[["a"]]

提示:

  • 1 <= s.length <= 16
  • s 仅由小写英文字母组成

思路:

要解决这个问题,可以使用回溯算法。回溯算法在这个问题中的应用主要是通过递归地选择每一个可能的回文子串,并在整个字符串中进行拆分,直到遍历完所有可能的组合。

回溯思路

  1. 回文判断:首先,需要一个辅助函数来判断一个子串是否是回文。这可以通过双指针法来实现,从字符串的两端向中间遍历,检查字符是否相同。

  2. 定义递归函数递归终止条件

      • start 等于字符串 s 的长度时,说明已经成功将字符串划分为回文子串,将 current_partition 添加到 result 中。
    • 递归过程
      • start 开始遍历字符串,尝试划分出每一个可能的回文子串。
      • 对于每一个子串,判断其是否为回文:
        • 如果是,则将其加入 current_partition,并对剩余部分继续递归划分。
        • 如果不是,则跳过该子串。
      • 回溯:在递归返回后,将最后一个子串从 current_partition 中移除,尝试下一个可能的划分

上代码:

class Solution {
public:vector<vector<string>> partition(string s) {vector<vector<string>> result;  // 存储所有的划分方案vector<string> current_partition;  // 当前的回文子串组合// 调用递归函数开始回溯backtrack(s, 0, current_partition, result);return result;}private:// 判断一个子串是否为回文bool isPalindrome(const string &s, int left, int right) {while (left < right) {if (s[left] != s[right]) return false;left++;right--;}return true;}// 回溯函数void backtrack(const string &s, int start, vector<string> &current_partition, vector<vector<string>> &result) {if (start == s.size()) {// 如果已经遍历完整个字符串,将当前划分加入结果result.push_back(current_partition);return;}for (int end = start; end < s.size(); ++end) {// 判断当前子串是否为回文if (isPalindrome(s, start, end)) {// 如果是回文,将其加入当前组合current_partition.push_back(s.substr(start, end - start + 1));// 继续递归处理剩余的字符串backtrack(s, end + 1, current_partition, result);// 回溯:移除最后一个加入的子串current_partition.pop_back();}}}
};

这篇关于代码随想录算法训练营第二十三天| 39. 组合总和的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1098276

相关文章

Java中的雪花算法Snowflake解析与实践技巧

《Java中的雪花算法Snowflake解析与实践技巧》本文解析了雪花算法的原理、Java实现及生产实践,涵盖ID结构、位运算技巧、时钟回拨处理、WorkerId分配等关键点,并探讨了百度UidGen... 目录一、雪花算法核心原理1.1 算法起源1.2 ID结构详解1.3 核心特性二、Java实现解析2.

Java中调用数据库存储过程的示例代码

《Java中调用数据库存储过程的示例代码》本文介绍Java通过JDBC调用数据库存储过程的方法,涵盖参数类型、执行步骤及数据库差异,需注意异常处理与资源管理,以优化性能并实现复杂业务逻辑,感兴趣的朋友... 目录一、存储过程概述二、Java调用存储过程的基本javascript步骤三、Java调用存储过程示

Visual Studio 2022 编译C++20代码的图文步骤

《VisualStudio2022编译C++20代码的图文步骤》在VisualStudio中启用C++20import功能,需设置语言标准为ISOC++20,开启扫描源查找模块依赖及实验性标... 默认创建Visual Studio桌面控制台项目代码包含C++20的import方法。右键项目的属性:

MySQL数据库的内嵌函数和联合查询实例代码

《MySQL数据库的内嵌函数和联合查询实例代码》联合查询是一种将多个查询结果组合在一起的方法,通常使用UNION、UNIONALL、INTERSECT和EXCEPT关键字,下面:本文主要介绍MyS... 目录一.数据库的内嵌函数1.1聚合函数COUNT([DISTINCT] expr)SUM([DISTIN

Java实现自定义table宽高的示例代码

《Java实现自定义table宽高的示例代码》在桌面应用、管理系统乃至报表工具中,表格(JTable)作为最常用的数据展示组件,不仅承载对数据的增删改查,还需要配合布局与视觉需求,而JavaSwing... 目录一、项目背景详细介绍二、项目需求详细介绍三、相关技术详细介绍四、实现思路详细介绍五、完整实现代码

Go语言代码格式化的技巧分享

《Go语言代码格式化的技巧分享》在Go语言的开发过程中,代码格式化是一个看似细微却至关重要的环节,良好的代码格式化不仅能提升代码的可读性,还能促进团队协作,减少因代码风格差异引发的问题,Go在代码格式... 目录一、Go 语言代码格式化的重要性二、Go 语言代码格式化工具:gofmt 与 go fmt(一)

HTML5实现的移动端购物车自动结算功能示例代码

《HTML5实现的移动端购物车自动结算功能示例代码》本文介绍HTML5实现移动端购物车自动结算,通过WebStorage、事件监听、DOM操作等技术,确保实时更新与数据同步,优化性能及无障碍性,提升用... 目录1. 移动端购物车自动结算概述2. 数据存储与状态保存机制2.1 浏览器端的数据存储方式2.1.

基于 HTML5 Canvas 实现图片旋转与下载功能(完整代码展示)

《基于HTML5Canvas实现图片旋转与下载功能(完整代码展示)》本文将深入剖析一段基于HTML5Canvas的代码,该代码实现了图片的旋转(90度和180度)以及旋转后图片的下载... 目录一、引言二、html 结构分析三、css 样式分析四、JavaScript 功能实现一、引言在 Web 开发中,

Python如何去除图片干扰代码示例

《Python如何去除图片干扰代码示例》图片降噪是一个广泛应用于图像处理的技术,可以提高图像质量和相关应用的效果,:本文主要介绍Python如何去除图片干扰的相关资料,文中通过代码介绍的非常详细,... 目录一、噪声去除1. 高斯噪声(像素值正态分布扰动)2. 椒盐噪声(随机黑白像素点)3. 复杂噪声(如伪

Java Spring ApplicationEvent 代码示例解析

《JavaSpringApplicationEvent代码示例解析》本文解析了Spring事件机制,涵盖核心概念(发布-订阅/观察者模式)、代码实现(事件定义、发布、监听)及高级应用(异步处理、... 目录一、Spring 事件机制核心概念1. 事件驱动架构模型2. 核心组件二、代码示例解析1. 事件定义