Java 遞迴演算法：從數字陣列中找出總和為指定值的所有組合

問題描述

給定一組整數（如 {12, 60, -8, 99, 15, 35, 17, 18}），找出所有任意數量元素相加等於目標值（如 35）的組合。

遞迴解法核心邏輯

1. 將輸入字串解析為整數陣列並排序。
2. 過濾掉大於目標值的元素（假設皆為正數時可優化）。
3. 對每個可能的組合長度（1 到 N），遞迴生成所有該長度的子集。
4. 計算子集總和，等於目標值則輸出。

完整程式碼

package test1;
import java.util.Arrays;

public class Demo {
    public static void main(String[] args) {
        String str = "12,60,-8,99,15,35,17,18,8,10,11,12";
        int sum = 35;
        diguiSum(str, sum);
    }

    public static void diguiSum(String str, int sum) {
        String[] x = str.split(",");
        int[] array = arrayTransform(x);
        for (int i = 0; i < array.length; i++) {
            int[] cache = new int[i + 1];
            cir(0, i, 0, array, cache, sum);
        }
    }

    private static void cir(int depth, int targetDepth, int start, int[] array, int[] cache, int sum) {
        for (int i = start; i < array.length; i++) {
            cache[depth] = array[i];
            if (depth == targetDepth) {
                if (getSum(cache) == sum) printCache(cache);
            } else {
                cir(depth + 1, targetDepth, i + 1, array, cache, sum);
            }
        }
    }

    private static int getSum(int[] cache) {
        int s = 0; for (int v : cache) s += v; return s;
    }

    private static void printCache(int[] cache) {
        for (int v : cache) System.out.print(v + ",");
        System.out.println();
    }

    private static int[] arrayTransform(String[] strArray) {
        int[] array = new int[strArray.length];
        for (int i = 0; i < strArray.length; i++) array[i] = Integer.parseInt(strArray[i]);
        Arrays.sort(array);
        int len = 0;
        for (int i = 0; i < array.length; i++) if (array[i] > 35) { len = i; break; }
        return Arrays.copyOf(array, len);
    }
}

執行結果示意

補充說明

• 此演算法屬於子集和問題，屬 NP-Complete，僅適合小規模資料集。
• 程式碼中針對正數目標值做了排序與截斷優化；若含負數則不可截斷。
• 可改用動態規劃或 Meet-in-the-Middle 優化大規模場景。