题目出处
题目描述

个人解法
思路:
todo
代码示例:(Java)
todo
复杂度分析
todo
官方解法
方法1:搜索回溯
思路:
对于这类寻找所有可行解的题,我们都可以尝试用「搜索回溯」的方法来解决。
回到本题,我们定义递归函数 dfs(target,combine,idx) 表示当前在 candidates 数组的第 idx 位,还剩 target 要组合,已经组合的列表为 combine。递归的终止条件为 target≤0 或者 candidates 数组被全部用完。那么在当前的函数中,每次我们可以选择跳过不用第 idx 个数,即执行 dfs(target,combine,idx+1)。也可以选择使用第 idx 个数,即执行 dfs(target−candidates[idx],combine,idx),注意到每个数字可以被无限制重复选取,因此搜索的下标仍为 idx。
更形象化地说,如果我们将整个搜索过程用一个树来表达,即如下图呈现,每次的搜索都会延伸出两个分叉,直到递归的终止条件,这样我们就能不重复且不遗漏地找到所有可行解:

当然,搜索回溯的过程一定存在一些优秀的剪枝方法来使得程序运行得更快,而这里只给出了最朴素不含剪枝的写法,因此欢迎各位读者在评论区分享自己的见解。
代码示例:(Java)
public class Solution1 {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> ans = new ArrayList<List<Integer>>();
List<Integer> combine = new ArrayList<Integer>();
dfs(candidates, target, ans, combine, 0);
return ans;
}
public void dfs(int[] candidates, int target, List<List<Integer>> ans, List<Integer> combine, int idx) {
if (idx == candidates.length) {
return;
}
if (target == 0) {
ans.add(new ArrayList<Integer>(combine));
return;
}
// 直接跳过
dfs(candidates, target, ans, combine, idx + 1);
// 选择当前数
if (target - candidates[idx] >= 0) {
combine.add(candidates[idx]);
dfs(candidates, target - candidates[idx], ans, combine, idx);
combine.remove(combine.size() - 1);
}
}
}
复杂度分析

考察知识点
1.排列组合
收获
Gitee源码位置
同名文章,已同步发表于CSDN,个人网站,公众号
FEATURED TAGS
Cursor
AI
蝇量模式
责任链模式
工厂设计模式
观察者设计模式
每日一个设计模式
Spring中的设计模式
策略设计模式
设计模式原则
设计模式分类
Redis数据类型及应用
分布式锁
spring循环依赖
SpringAop
工一影单
书单
AQS
LockSupport
两数之和
字节跳动
leetcode
58同城
经典书籍
深入理解Java虚拟机
OpenJDK
Java基础
GitHub的骚操作
彩蛋
JDK
JVM性能分析工具
JVM监控
CPU占用过高解决思路
Linux常用命令
线上故障分析
G1垃圾收集器
垃圾收集器生产配置
默认的垃圾收集器
垃圾收集器
GC垃圾回收算法
OOM
虚引用
弱引用
软引用
强引用
Java的四大引用
jvm常用基本配置参数
JVM参数配置
JVM系统默认值
JVM调优
GC Roots
JVM垃圾回收
常见的垃圾回收算法
GC的作用域
JVM内存结构
ThreadPoolExecutor
线程池
阻塞队列
Semaphore
CyclicBarrier
CountDownLatch
自旋锁
Java锁
线程安全
ArrayList
原子更新
原子引用
ABA
AtomicInteger
CAS
高并发
多线程
juc
数据库连接工具
程序员简历
activeMQ
异步
消息队列
购物车
京东
分布式系统
单点登陆
集群
zookeeper
搜素引擎
solr
es
IO
数据结构
Redis
算法
GC
JVM
索引
MySQL
Redis持久化
git
Centos
服务类命令
Linux
字段不一致
MyBatis
工作流程
原理
post请求乱码
SpringMVC
传播属性
隔离级别
数据库事务
笔记
大数据
前端
Java
Bean作用域
Spring
JavaEE
Java变量
循环迭代
递归
循环与迭代
方法参数传递
类的实例化
类的初始化
设计模式
自增变量
面试题
JavaSE
安装教程
教程
