力扣39题：组合总和的 Java 实现

---

引言

力扣（LeetCode）是一个在线编程平台，提供了大量的编程题目供开发者练习。第39题“组合总和”是一个经典的回溯算法问题，要求找出所有可能的组合，使得组合中的数字之和等于给定的目标值。本文将介绍如何使用 Java 解决这个问题。

题目描述

给定一个无重复元素的数组 candidates 和一个目标数 target，找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的数字可以无限制重复被选取。

示例：

输入: candidates = [2,3,6,7], target = 7,
输出: 
[
  [7],
  [2,2,3]
]

说明：

• 所有数字（包括目标数）都是正整数。
• 解集不能包含重复的组合。

问题分析

这个问题可以通过回溯算法来解决。回溯算法是一种通过试错的方式，逐步逼近问题解的方法。在这个问题中，我们需要：

1. 从左到右遍历数组。
2. 每次选择一个数字，并将其添加到当前组合中。
3. 检查当前组合的和是否等于目标值。
4. 如果等于目标值，将当前组合添加到结果集中。
5. 继续选择下一个数字，直到所有数字都被尝试过。

Java 实现

以下是使用 Java 解决这个问题的代码实现：

class Solution {
    List<List<Integer>> result=new ArrayList<>();
    List<Integer> path=new LinkedList<>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        getConsistNum(candidates,target,0,0);
        return result;
    }
    public void getConsistNum(int[] candidates,int target,int sum,int startIndex){
        if(sum==target){
            result.add(new ArrayList<>(path));
            return;
        }
        for(int i=startIndex;i<candidates.length;i++){
            if(sum+candidates[i]>target) break;
            path.add(candidates[i]);
            sum+=candidates[i];
            getConsistNum(candidates,target,sum,i);
            sum-=candidates[i];
            path.remove(path.size()-1);
        }
    }
}

代码解释

1. combinationSum 方法：这是主方法，接收数组 candidates 和目标值 target。
2. getConsistNumk 方法：这是一个递归方法，用于实现回溯算法。
   • candidates：当前考虑的数组。
   • target：剩余的目标值。
   • result：存储所有有效组合的列表。
   • path：当前的组合。
   • start：从数组的哪个位置开始选择数字。
3. 排序：对数组进行排序，可以优化搜索过程，避免重复组合。
4. 递归终止条件：当目标值等于sum时，表示找到一个有效的组合，将其添加到结果集中。
5. 回溯：在每次递归调用结束后，通过移除 path 中的最后一个元素来实现回溯。

结语

通过本文的介绍，你应该已经了解了如何使用 Java 解决力扣第39题“组合总和”。这个问题是一个很好的练习回溯算法的机会。希望本文能够帮助你更好地理解和掌握回溯算法。如果你有任何问题或需要进一步的帮助，请随时在评论区提问。

---

原文地址：https://blog.csdn.net/2301_77695569/article/details/140675074

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！