java如何求組合總和

Java如何求組合總和

在算法和編程中，組合總和問題是一個經典的問題。給定一個候選數字的集合和一個目標數，要求找出所有候選數字的組合，使得這些數字的和等于目標數。每個數字可以被無限次使用，且組合中的數字可以按任意順序排列。本文將介紹如何使用Java來解決這個問題。

問題描述

給定一個無重復元素的整數數組 candidates 和一個目標整數 target，找出所有 candidates 中可以使數字和為 target 的組合。candidates 中的數字可以無限制重復被選取。

示例：

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

解決思路

這個問題可以通過回溯算法來解決?；厮菟惴ㄊ且环N通過遞歸來遍歷所有可能的解的方法。在每一步中，我們選擇一個候選數字，并將其加入到當前組合中，然后遞歸地繼續尋找剩余的目標數。如果當前組合的和等于目標數，則將其加入到結果集中。如果當前組合的和超過了目標數，則回溯到上一步，嘗試其他候選數字。

代碼實現

以下是使用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 中的最后一個數字，嘗試其他候選數字。

總結

通過回溯算法，我們可以有效地解決組合總和問題?；厮菟惴ǖ年P鍵在于遞歸地嘗試所有可能的組合，并在每一步中進行剪枝，以避免不必要的計算。Java的實現簡潔明了，適合初學者理解和掌握。希望本文能幫助你更好地理解如何用Java解決組合總和問題。