Java如何求组合总和

在算法和编程中，组合总和问题是一个经典的问题。给定一个候选数字的集合和一个目标数，要求找出所有候选数字的组合，使得这些数字的和等于目标数。每个数字可以被无限次使用，且组合中的数字可以按任意顺序排列。本文将介绍如何使用Java来解决这个问题。

问题描述

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

示例：

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

解决思路

这个问题可以通过回溯算法来解决。回溯算法是一种通过递归来遍历所有可能的解的方法。在每一步中，我们选择一个候选数字，并将其加入到当前组合中，然后递归地继续寻找剩余的目标数。如果当前组合的和等于目标数，则将其加入到结果集中。如果当前组合的和超过了目标数，则回溯到上一步，尝试其他候选数字。

代码实现

以下是使用Java实现的组合总和问题的解决方案：

import java.util.ArrayList;
import java.util.List;

public class CombinationSum {

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(result, new ArrayList<>(), candidates, target, 0);
        return result;
    }

    private void backtrack(List<List<Integer>> result, List<Integer> tempList, int[] candidates, int remain, int start) {
        if (remain < 0) {
            return;
        } else if (remain == 0) {
            result.add(new ArrayList<>(tempList));
        } else {
            for (int i = start; i < candidates.length; i++) {
                tempList.add(candidates[i]);
                backtrack(result, tempList, candidates, remain - candidates[i], i); // 允许重复使用同一个数字
                tempList.remove(tempList.size() - 1); // 回溯
            }
        }
    }

    public static void main(String[] args) {
        CombinationSum solution = new CombinationSum();
        int[] candidates = {2, 3, 6, 7};
        int target = 7;
        List<List<Integer>> result = solution.combinationSum(candidates, target);
        System.out.println(result);
    }
}

代码解析

1. combinationSum 方法：这是主方法，初始化结果集 result 并调用 backtrack 方法开始回溯过程。

2. backtrack 方法：这是核心的回溯方法。它接受以下参数：

   • result：存储所有符合条件的组合。
   • tempList：当前正在构建的组合。
   • candidates：候选数字数组。
   • remain：剩余的目标数。
   • start：当前递归的起始位置，用于避免重复组合。

3. 递归终止条件：

   • 如果 remain < 0，说明当前组合的和已经超过了目标数，直接返回。
   • 如果 remain == 0，说明当前组合的和等于目标数，将其加入到结果集中。

4. 递归过程：

   • 遍历候选数字，将当前数字加入到 tempList 中。
   • 递归调用 backtrack 方法，继续寻找剩余的目标数。
   • 回溯：移除 tempList 中的最后一个数字，尝试其他候选数字。

总结

通过回溯算法，我们可以有效地解决组合总和问题。回溯算法的关键在于递归地尝试所有可能的组合，并在每一步中进行剪枝，以避免不必要的计算。Java的实现简洁明了，适合初学者理解和掌握。希望本文能帮助你更好地理解如何用Java解决组合总和问题。