这是超级幼稚的解决方案，它仅在输入数组上生成一个幂集，然后对每个集进行迭代以查看总和是否满足给定的总数。
在时间和空间上为O（2 n）。毛。
您可以使用a的想法
Set将所有索引存储到数组中，然后生成这些索引的所有排列，然后使用每个索引集返回到数组中并获取值。
输入项
- 目标：
10
- 值：
[3, 5, 5, 7]
码：
import java.util.*;import java.lang.*;import java.io.*;class SubsetSum{ public static <T> Set<Set<T>> powerSet(Set<T> originalSet) { Set<Set<T>> sets = new HashSet<Set<T>>(); if (originalSet.isEmpty()) { sets.add(new HashSet<T>()); return sets; } List<T> list = new ArrayList<T>(originalSet); T head = list.get(0); Set<T> rest = new HashSet<T>(list.subList(1, list.size())); for (Set<T> set : powerSet(rest)) { Set<T> newSet = new HashSet<T>(); newSet.add(head); newSet.addAll(set); sets.add(newSet); sets.add(set); } return sets; } public static void main(String[] args) { Set<Integer> mySet = new HashSet<Integer>(); int[] arr={3, 5, 5, 7}; int target = 10; int numVals = 4; for(int i=0;i<numVals;++i) { mySet.add(i); } System.out.println("Solutions: "); for (Set<Integer> s : powerSet(mySet)) { int sum = 0; for (Integer e : s) { sum += arr[e]; } if (sum == target) { String soln = "[ "; for (Integer e : s) { soln += arr[e]; soln += " "; } soln += "]"; System.out.println(soln); } } }}输出量
解决方案：
[5 5]
[3 7]
现场演示
一旦了解了这一点，也许您就可以准备开始分支定界或近似方法了。
