当前位置：首页 > backend >正文

2025年- H71-Lc179--39.组合总和(回溯,组合）--Java版

backend 2025/6/28 13:00:11

1.题目描述

在这里插入图片描述

2.思路

当前的元素可以重复使用。
（1）确定回溯算法函数的参数和返回值（一般是void类型）
（2）因为是用递归实现的，所以我们要确定终止条件
（3）单层搜索逻辑
二维数组存结果集，一维数组存放单一节点。
组合也就是收集路径的过程。
补充： toString()：当你需要将对象转换为字符串形式（例如将对象内容拼接到其它字符串中），你可以显式调用 toString()。
原始类型：不能直接调用 toString()，但可以通过 Integer.toString(), String.valueOf() 等方法转换为字符串。

对象类型：可以调用 toString() 方法，将对象转为字符串。大多数 Java 内建类（如 String, List）已经重写了 toString() 方法来提供默认的字符串表示。你也可以在自定义类中重写 toString() 方法来提供自定义的字符串输出。

在这里插入图片描述

3.代码实现

import java.util.ArrayList;
import java.util.List;public class H39 {public List<List<Integer>> combinationSum(int[] candidates, int target) {int sum=0;List<List<Integer>> res=new ArrayList<>();List<Integer> cur=new ArrayList<>();backtracking(res,cur,candidates,target,0);return res;}public void backtracking(List<List<Integer>> res,List<Integer> cur,int[] candidates,int target,int startIndex){ // 终止条件：如果目标值为0，找到一个组合.检查的是当前组合的和是否等于 target，而不是当前组合的长度。if(target==0){//引用问题：cur 是引用类型，直接将它添加到 res 会导致多个组合之间共享同一个 cur 对象，后续的修改会影响已存储的组合。//副本问题：通过 new ArrayList<>(cur) 创建 cur 的副本，确保每个组合在存储时是独立的，不受后续递归的影响。res.add(new ArrayList<>(cur)); // 添加 cur 的副本}for(int i=startIndex;i<candidates.length;i++){int num=candidates[i];// 如果当前数字大于目标值，则跳过，因为之后的数字都更大if(num>target)continue;// 选择当前数字，加入到组合中cur.add(num);// 递归调用，目标值减去当前选择的数字
//            startIndex 确保每次递归都从当前索引开始，允许重复使用同一个数字。
//
//            每次递归调用时，目标值 target 减去当前数字 num，继续寻找符合条件的组合。backtracking(res,cur,candidates,target-num,i);//回溯cur.remove(cur.size()-1);}}public static void main(String[] args){H39 test=new H39();int[] candidates = {2,3,6,7};int target = 7;List<List<Integer>> ans=test.combinationSum(candidates,target);System.out.print(ans);}
}