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

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);


    }
}