LeetCode第39题之Combination Sum(两种方法)

2024-06-20 15:18

本文主要是介绍LeetCode第39题之Combination Sum(两种方法),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

思路:两种方法都是利用递归回溯,第二方法在第一种方法的基础上对原始数据先进行排序,这样可以剪枝,加快计算速度。第一种方法在LeetCode上测试运行的时间是24ms,第二种方法运行时间为16ms。
方法一:

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;class Solution {
private://res保存满足题意的结果vector<vector<int>> res;//保存当前的一种方案vector<int> method;
public:void getCombinationSum(int start, int sum, int target, vector<int> &candidates){//因为canditates经过排序,所以如果sum>targetif (sum > target){return;}//如果满足题意则保存结果else if (sum == target){res.push_back(method);return;} else{for(int i=start;i<candidates.size();++i){//芳第i件物品method.push_back(candidates[i]);getCombinationSum(i, sum+candidates[i], target, candidates);//回溯,去除第i件物品,然后继续放第i+1个数method.pop_back();}}}vector<vector<int>> combinationSum(vector<int>& candidates, int target) {int sum = 0;getCombinationSum(0, 0, target, candidates);return res;}
};int main()
{Solution s;vector<int> canditates;canditates.push_back(2);canditates.push_back(7);canditates.push_back(3);canditates.push_back(6);vector<vector<int>> res = s.combinationSum(canditates, 7);//打印结果for (vector<vector<int>>::iterator ita=res.begin();ita!=res.end();++ita){for (vector<int>::iterator itb=ita->begin();itb!=ita->end();++itb){cout<<*itb<<'\t';}cout<<endl;}cout<<endl;return 0;
}

方法二:

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;class Solution {
private://res保存满足题意的结果vector<vector<int>> res;//保存当前的一种方案vector<int> method;
public:void getCombinationSum(int start, int sum, int target, vector<int> &candidates){for(int i=start;i<candidates.size();++i){//放第i个数,如果第i个数放进去之后超过了target,则剪枝(直接返回),因为candidates经过排序,换成后面的数放进去的话肯定也会超过targetif (sum+candidates[i] > target){return;}//如果满足则保存结果else if (sum+candidates[i] == target){method.push_back(candidates[i]);res.push_back(method);method.pop_back();return;}//如果放第i个数后不超过target,则将第i个数放入else{method.push_back(candidates[i]);getCombinationSum(i, sum+candidates[i], target, candidates);//回溯,去除第i个数,然后继续放第i+1个数method.pop_back();}                   }}vector<vector<int>> combinationSum(vector<int>& candidates, int target) {int sum = 0;//排序sort(candidates.begin(), candidates.end());getCombinationSum(0, 0, target, candidates);return res;}
};int main()
{Solution s;vector<int> canditates;canditates.push_back(2);canditates.push_back(7);canditates.push_back(3);canditates.push_back(6);vector<vector<int>> res = s.combinationSum(canditates, 7);for (vector<vector<int>>::iterator ita=res.begin();ita!=res.end();++ita){for (vector<int>::iterator itb=ita->begin();itb!=ita->end();++itb){cout<<*itb<<'\t';}cout<<endl;}cout<<endl;return 0;
}

这篇关于LeetCode第39题之Combination Sum(两种方法)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


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

相关文章

在MySQL中实现冷热数据分离的方法及使用场景底层原理解析

《在MySQL中实现冷热数据分离的方法及使用场景底层原理解析》MySQL冷热数据分离通过分表/分区策略、数据归档和索引优化,将频繁访问的热数据与冷数据分开存储,提升查询效率并降低存储成本,适用于高并发... 目录实现冷热数据分离1. 分表策略2. 使用分区表3. 数据归档与迁移在mysql中实现冷热数据分

Spring Boot从main方法到内嵌Tomcat的全过程(自动化流程)

《SpringBoot从main方法到内嵌Tomcat的全过程(自动化流程)》SpringBoot启动始于main方法,创建SpringApplication实例,初始化上下文,准备环境,刷新容器并... 目录1. 入口:main方法2. SpringApplication初始化2.1 构造阶段3. 运行阶

Olingo分析和实践之ODataImpl详细分析(重要方法详解)

《Olingo分析和实践之ODataImpl详细分析(重要方法详解)》ODataImpl.java是ApacheOlingoOData框架的核心工厂类,负责创建序列化器、反序列化器和处理器等组件,... 目录概述主要职责类结构与继承关系核心功能分析1. 序列化器管理2. 反序列化器管理3. 处理器管理重要方

Python错误AttributeError: 'NoneType' object has no attribute问题的彻底解决方法

《Python错误AttributeError:NoneTypeobjecthasnoattribute问题的彻底解决方法》在Python项目开发和调试过程中,经常会碰到这样一个异常信息... 目录问题背景与概述错误解读:AttributeError: 'NoneType' object has no at

postgresql使用UUID函数的方法

《postgresql使用UUID函数的方法》本文给大家介绍postgresql使用UUID函数的方法,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录PostgreSQL有两种生成uuid的方法。可以先通过sql查看是否已安装扩展函数,和可以安装的扩展函数

Java中Arrays类和Collections类常用方法示例详解

《Java中Arrays类和Collections类常用方法示例详解》本文总结了Java中Arrays和Collections类的常用方法,涵盖数组填充、排序、搜索、复制、列表转换等操作,帮助开发者高... 目录Arrays.fill()相关用法Arrays.toString()Arrays.sort()A

Nginx安全防护的多种方法

《Nginx安全防护的多种方法》在生产环境中,需要隐藏Nginx的版本号,以避免泄漏Nginx的版本,使攻击者不能针对特定版本进行攻击,下面就来介绍一下Nginx安全防护的方法,感兴趣的可以了解一下... 目录核心安全配置1.编译安装 Nginx2.隐藏版本号3.限制危险请求方法4.请求限制(CC攻击防御)

python生成随机唯一id的几种实现方法

《python生成随机唯一id的几种实现方法》在Python中生成随机唯一ID有多种方法,根据不同的需求场景可以选择最适合的方案,文中通过示例代码介绍的非常详细,需要的朋友们下面随着小编来一起学习学习... 目录方法 1:使用 UUID 模块(推荐)方法 2:使用 Secrets 模块(安全敏感场景)方法

MyBatis-Plus通用中等、大量数据分批查询和处理方法

《MyBatis-Plus通用中等、大量数据分批查询和处理方法》文章介绍MyBatis-Plus分页查询处理,通过函数式接口与Lambda表达式实现通用逻辑,方法抽象但功能强大,建议扩展分批处理及流式... 目录函数式接口获取分页数据接口数据处理接口通用逻辑工具类使用方法简单查询自定义查询方法总结函数式接口

MySQL深分页进行性能优化的常见方法

《MySQL深分页进行性能优化的常见方法》在Web应用中,分页查询是数据库操作中的常见需求,然而,在面对大型数据集时,深分页(deeppagination)却成为了性能优化的一个挑战,在本文中,我们将... 目录引言:深分页,真的只是“翻页慢”那么简单吗?一、背景介绍二、深分页的性能问题三、业务场景分析四、