LeetCode刷题之HOT100之组合总和

2024/6/3 周一，工作日的第一天。昨晚梦到被导师说去实验室不积极哈哈哈，风扇开到二级，早上被吹醒。买的书马上快要到了。上午刚来准备刷题，结果去搞了一下数据库sql，做的差不多了，还差点格式转换就差不多出回来了。现在来做题。

1、题目描述

2、逻辑分析

无重复数组，给一个目标值target，要求在数组中找出可以使数字和等于target的所有不同组合，且数组中的元素可以被重复使用。那么怎么解呢？我没有头绪，看看题解怎么说。官方题解给出算法是使用搜索回溯的方法，里面涉及到深度优先搜索递归计算。大致思路：将整个搜索过程用一个树来表达，即如下图呈现，每次的搜索都会延伸出两个分叉，直到递归的终止条件，这样我们就能不重复且不遗漏地找到所有可行解：

像上图中所示：一个个数计算，这样就不会有被遗漏的元素了。下面看具体代码实现。

3、代码演示

public List<List<Integer>> combinationSum(int[] candidates, int target) {
// 创建一个结果列表，用于存储所有可能的组合
List<List<Integer>> res = new ArrayList<List<Integer>>();
// 创建一个临时列表，用于存储当前正在构建的组合
List<Integer> combina = new ArrayList<>();
// 调用深度优先搜索方法，开始搜索所有可能的组合
dfs( candidates,  target, res , combina, 0);
// 返回结果列表 
return res;
}
// 深度优先搜索方法，用于递归地搜索所有可能的组合
public void dfs(int[] candidates, int target, List<List<Integer>> res , List<Integer> combina, int index){
// 如果已经遍历完所有的候选数字，则直接返回
if(index == candidates.length){
return;
}
// 如果当前组合的数字之和已经等于目标值target，则将当前组合添加到结果列表中，并返回 
if(target == 0){
res.add(new ArrayList<Integer> (combina));
return;
}
// 不选择当前数字，继续搜索下一个数字
dfs(candidates, target, res, combina, index + 1);
// 如果目标值target减去当前数字仍然大于等于0，则可以选择当前数字
if(target - candidates[index] >= 0){
// 将当前数字添加到当前组合中 
combina.add(candidates[index]);
// 递归调用dfs，目标值变为target减去当前数字 
dfs(candidates,target - candidates[index], res, combina, index);
// 回溯，将当前数字从组合中移除，以便尝试其他组合
combina.remove(combina.size() - 1);
}
}

时间复杂度：O(S)，其中 S 为所有可行解的长度之和。空间复杂度：O(target)。
边看边敲完这段代码，大致意思明了，但是对一些细枝末节的地方还是稍有欠缺，先放一放，下次再来看看。搞了几天的后端结果发现搞错了哈哈，只能重新开始啦，悲惨滴我呜呜呜。再见啦！