实际上，我认为您确实想要字典顺序，但要降序而不是升序。此外：
- 从您的描述中我不清楚 A，B，... D 在您的答案中扮演任何角色（可能作为值的容器除外）。
- 我认为您的问题示例只是“对于每个至少 5 个整数，最多两个值的最大可能总数，{3, 3, 2, 1} 集合中有多少不同的对具有该整数的总和？”
- 有趣的部分是早期救助，一旦无法达成任何可能的解决方案（剩余可实现的金额太小）。
稍后我将发布示例代码。
这是我承诺的示例代码，以下是一些注释：
public class Combos {
/* permanent state for instance */
private int values[];
private int length;
/* transient state during single "count" computation */
private int n;
private int limit;
private Tally<Integer> tally;
private int best[][]; // used for early-bail-out
private void initializeForCount(int n, int limit) {
this.n = n;
this.limit = limit;
best = new int[n+1][length+1];
for (int i = 1; i <= n; ++i) {
for (int j = 0; j <= length - i; ++j) {
best[i][j] = values[j] + best[i-1][j+1];
}
}
}
private void countAt(int left, int start, int sum) {
if (left == 0) {
tally.inc(sum);
} else {
for (
int i = start;
i <= length - left
&& limit <= sum + best[left][i]; // bail-out-check
++i
) {
countAt(left - 1, i + 1, sum + values[i]);
}
}
}
public Tally<Integer> count(int n, int limit) {
tally = new Tally<Integer>();
if (n <= length) {
initializeForCount(n, limit);
countAt(n, 0, 0);
}
return tally;
}
public Combos(int[] values) {
this.values = values;
this.length = values.length;
}
}
前言备注：
这使用了一个名为 Tally 的小助手类，它只是隔离了列表（包括对从未见过的键进行初始化）。我会把它放在最后。
为了保持简洁，我采用了一些对“真实”代码来说不是好的做法的捷径：
- 这不会检查空值数组等。
- 我假设值数组已经按降序排序，这是早期救助技术所必需的。（好的生产代码将包括排序。）
- 我将瞬态数据放入实例变量中，而不是将它们作为参数传递给支持
count. 这使得这个类是非线程安全的。
解释：
的实例Combos是使用要组合的（降序）整数数组创建的。该value数组为每个实例设置一次，但count可以使用不同的人口规模和限制进行多次调用。
该count方法触发（大部分）标准递归遍历n来自values. 该limit论点给出了利息总和的下限。
该countAt方法检查来自 的整数组合values。left参数是剩余多少整数来构成n总和中的整数，是start要values搜索的位置，并且sum是部分总和。
早期救助机制基于计算best，一个二维数组，指定从给定状态可达到的“最佳”总和。in的值是从原始位置开始best[n][p]的值的最大总和。npvalues
countAt当积累了正确的人口时，触底的递归；这会将当前sum（n值）添加到tally. 如果countAt还没有触底，values则从start-ing 位置扫过增加当前的 partial sum，只要：
- 留有足够的职位
values以达到指定的人口数量，并且
- 剩余的
best（最大）小计足够大，可以使limit.
使用您的问题数据运行的示例：
int[] values = {3, 3, 2, 1};
Combos mine = new Combos(values);
Tally<Integer> tally = mine.count(2, 5);
for (int i = 5; i < 9; ++i) {
int n = tally.get(i);
if (0 < n) {
System.out.println("found " + tally.get(i) + " sums of " + i);
}
}
产生您指定的结果：
found 2 sums of 5
found 1 sums of 6
这是理货代码：
public static class Tally<T> {
private Map<T,Integer> tally = new HashMap<T,Integer>();
public Tally() {/* nothing */}
public void inc(T key) {
Integer value = tally.get(key);
if (value == null) {
value = Integer.valueOf(0);
}
tally.put(key, (value + 1));
}
public int get(T key) {
Integer result = tally.get(key);
return result == null ? 0 : result;
}
public Collection<T> keys() {
return tally.keySet();
}
}