Sum-of-Subsets

Java code:

import java.util.LinkedList;
import java.util.List;

public class SumOfSubsets {
    static int[] nums = {2, 10, 13, 17, 22, 42};
    static List<Integer> ansList = new LinkedList<Integer>();
    
    public static void main(String[] args) {
        int totalWeight = 52;
        
        System.out.println("以下是所有的解:");
        findAns(totalWeight, 0);
    }

    private static void findAns(int restWeight, int startIndex) {
        if (restWeight > 0) {
            for (int i=startIndex; i<nums.length; i++) {
                ansList.add(nums[i]);
                findAns(restWeight - nums[i], i + 1);
                ansList.remove(ansList.size() - 1);
            }    
        }
        else if (restWeight == 0) {
            for (int i: ansList)
                System.out.print(i + " ");
            System.out.println();
        }
    }
}

範例輸入輸出:

---

此程式解決的問題是Sum-of-Subsets問題，問題是給一個數字集合S還有一個數字N，找出S裡面所有加起來總和會等於N的組合。解法就是窮舉所有的加法組合看看那一組有符合上述條件。

此程式是解決課本第5章第13題的問題，所以參數已經設死在程式裡。輸出結果就是所有總和為52的組合。