组合总和类题目汇总

news/2025/1/22 5:35:56/

刷leetcode时遇到好几个组合总和类题目,在这里汇总归纳一下

  1. leetcode算法题–组合总和 Ⅳ
  2. 零钱兑换 II
  3. leetcode算法题–组合总和

一般这类题目有两种做法,动态规划或者是dfs。一般如果题目只要求一个组合数,那么一般就使用动态规划做,因为题目会对时间复杂度会做一定限制,使用dfs一般过不了,如第1、2题。如果题目要求组合排列,那么可以使用dfs做,此时题目会对时间复杂度做一定放宽,如第3题。并且这类题目都是可以重复使用数,但是对不同顺序数字排列是否视为不同的组合将题目又分为两类,视为相同,如第2题;视为不同,如第1题。这导致了第1题和第2题的做法有细微不同,非常巧妙。

动态规划思路

先比较第1题和第2题的代码

// 组合总和IV
func combinationSum4(nums []int, target int) int {dp :=make([]int, target+1)dp[0] = 1for i := 1; i <= target; i ++ {for _, num := range nums {if num <= i {dp[i] += dp[i-num]} }}return dp[target]
}
// 零钱兑换II
func change(amount int, coins []int) int {dp := make([]int, amount+1)dp[0] = 1for _, coin := range coins { //每出现一个新的硬币刷新dpfor i := coin; i <= amount; i ++ {dp[i] += dp[i-coin]}}return dp[amount]
}

很容易发现,如果对不同顺序数字排列是否视为不同,则数组中数就不可以重复使用,于是放在外层循环,反之放在内层循环。

dfs思路

dfs思路其实也比较明显,比较值得注意的是这个idx的传入,可以让dfs不走回头路。

func combinationSum(candidates []int, target int) [][]int {res := make([][]int, 0)n := len(candidates)var dfs func(nums []int, target, idx int)dfs = func(nums []int, target, idx int) {if target == 0 {tmp := make([]int, len(nums)) copy(tmp, nums)res = append(res, tmp)return }for i := idx ; i < n; i ++ {c := candidates[i]if target - c >= 0{nums = append(nums, c)dfs(nums, target-c, i) nums = nums[:len(nums)-1] }} }dfs([]int{}, target, 0)return res
}
文章来源:https://blog.csdn.net/qq_20817327/article/details/134950207
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.ppmy.cn/news/1267025.html

相关文章

深入浅出接口测试原理及步骤

那么接口是什么&#xff1f; 软件开发&#xff0c;既要做前端&#xff0c;也要做后端&#xff0c;并且后端是整个业务的核心&#xff0c;用于处理业务请求&#xff0c;实现具体的功能&#xff1b;而前端只是提供一个页面给用户看结果以及提供页面给用户做输入。所以整个业务的…

图文教程:stable-diffusion的基本使用教程 txt2img(多图)

之前我介绍了SD的安装过程&#xff0c;那么这篇将介绍怎么使用SD 使用模型 SD安装好之后&#xff0c;我们只有一个默认的模型。这个模型很难满足我们的绘图需求&#xff0c;那么有2种方法。 1是自己训练一个模型&#xff08;有门槛&#xff09;2是去网站上找一个别人练好的模…

分布式环境认证和授权-基于springboot+JWT+拦截器实现-实操+源码下载

1、功能概述&#xff1f; 1、当用户登录的时候&#xff0c;将用户的信息通过JWT进行加密和签名&#xff0c;并将JWT产生了token信息保存到当前浏览器的localStoragee中,即本地存储中。 2、当用户登录成功后&#xff0c;访问其他资源的时候&#xff0c;程序从localStorage中获…

PHP是什么?

PHP&#xff08;Hypertext Preprocessor&#xff09;是一种广泛用于服务器端Web开发的开源脚本语言。最初由Rasmus Lerdorf于1994年创建&#xff0c;并于1995年发布了第一个版本。PHP语言的设计初衷是用于处理动态网页&#xff0c;尤其是用于构建Web应用程序。 PHP脚本通过嵌入…

物联网安全芯片ACL16 采用 32 位内核,片内集成多种安全密码模块 且低成本、低功耗

ACL16 芯片是研制的一款32 位的安全芯片&#xff0c;专门面向低成本、低功耗的应用领域&#xff0c; 特别针对各类 USB KEY 和安全 SE 等市场提供完善而有竞争力的解决方案。芯片采用 32 位内核&#xff0c;片内集成多种安全密码模块&#xff0c;包括SM1、 SM2、SM3、 SM4 算法…

Windows 11安装xray

需要先安装python&#xff0c;我这里已经安装好了&#xff0c;在命令行里边使用python --version可以看到自己的python版本。 xray的下载网址为https://github.com/chaitin/xray/releases&#xff0c;我根据自己的笔记本电脑配置&#xff0c;选择下载xray_windows_amd64.exe.…

算法基础之分解质因数

分解质因数 核心思想&#xff1a;试除法(从小到大枚举所有数) #include<iostream>#include<algorithm>using namespace std;void div(int n){for(int i2;i<n/i;i){if(n%i 0) //找到最小质数i{int s0;while(n%i 0){n/i;s; //记录指数}cout<<i<<&…

三天精通Selenium Web 自动化 - 项目实战环境准备

1 部署TestNG 返回 TestNG&#xff0c;即Testing Next Generation&#xff0c;下一代测试技术&#xff0c;是一套根据JUnit和NUnit思想而构建的利用注释来强化测试功能的一个测试框架&#xff0c;即可以用来做单元测试&#xff0c;也可以用来做集成测试。更多细节可以到官网去…