对于这种问题，通常将使用动态编程。但是，本质上可以归结为保留一组可能的总和，然后将输入值一个接一个地添加，如下面的代码所示，并且具有相同的渐近运行时间：
O(nK)，其中
n输入数组的大小和
K目标值。
但是，以下版本中的常量可能更大，但我认为代码比动态编程版本容易遵循。
public class Test { public static void main(String[] args) { int K = 44; List<Integer> inputs = Arrays.asList(19,23,41,5,40,36); int opt = 0; // optimal solution so far Set<Integer> sums = new HashSet<>(); sums.add(opt); // loop over all input values for (Integer input : inputs) { Set<Integer> newSums = new HashSet<>(); // loop over all sums so far for (Integer sum : sums) { int newSum = sum + input; // ignore too big sums if (newSum <= K) { newSums.add(newSum); // update optimum if (newSum > opt) { opt = newSum; } } } sums.addAll(newSums); } System.out.println(opt); }}编辑
关于运行时间的简短说明可能会很有用，因为我只是声称
O(n K)没有理由。
显然，初始化和打印结果只需要花费恒定的时间，因此我们应该分析双重循环。
外循环遍历所有输入，因此它的主体执行
n时间。
内循环遍及到目前为止的所有和，理论上它可能是一个指数数。 但是 ，我们使用的上限
K，因此中的所有值
sums都在范围内
[0,K]。由于
sums是集合，因此最多包含
K+1元素。
内循环内的所有计算都需要恒定的时间，因此总循环需要
O(K)。出于相同的原因，该集合
newSums也最多包含
K+1元素，因此
addAll最后也要使用
O(K)。
总结：外循环执行
n时间。循环体取
O(K)。因此，该算法在中运行
O(n K)。
编辑2
根据要求还查找导致最佳总和的元素：
除了跟踪单个整数（子列表的总和）之外，还应该跟踪子列表本身。如果您创建一个新类型，则这相对简单（没有getter / setter来简化示例）：
public class SubList { public int size; public List<Integer> subList; public SubList() { this(0, new ArrayList<>()); } public SubList(int size, List<Integer> subList) { this.size = size; this.subList = subList; }}初始化现在变为：
SubList opt = new SubList();Set<SubList> sums = new HashSet<>();sums.add(opt);
sums需求的内部循环也需要一些小的调整：
for (Integer input : inputs) { Set<SubList> newSums = new HashSet<>(); // loop over all sums so far for (SubList sum : sums) { List<Integer> newSubList = new ArrayList<>(sum.subList); newSubList.add(input); SubList newSum = new SubList(sum.size + input, newSubList); // ignore too big sums if (newSum.size <= K) { newSums.add(newSum); // update optimum if (newSum.size > opt) { opt = newSum; } } } sums.addAll(newSums);}
