由于没有其他人尝试过，我不妨至少提供一个部分解决方案。正如我在之前的评论中指出的那样，这个问题是子集和问题的一个变体，我在开发这个解决方案时严重依赖于该问题的文档化方法。
我们正在尝试编写一个函数subsetsWithSum(A, k, s)来计算 A 的所有 k 长度子集，总和为 s。这个问题以两种方式适用于递归解决方案：
- subsetsWithSum(x 1 ... x n , k, s) 的解可以通过计算 subsetsWithSum(x 2 ... x n , k, s) 并添加包括 x 1的所有有效子集（如果有）来找到; 和
- 可以通过计算 subsetsWithSum(A - x i , k-1, sx i ) 并将 x i添加到结果的每个子集（如果有）来找到包含元素 x i的所有有效子集。
递归的基本情况发生在 k 为 1 时，在这种情况下，subsetsWithSum(A, 1, s) 的解是该元素等于 s 的所有单元素子集的集合。
所以第一次尝试解决方案是
/**
* Return all k-length subsets of A starting at offset o that sum to s.
* @param A - an unordered list of integers.
* @param k - the length of the subsets to find.
* @param s - the sum of the subsets to find.
* @param o - the offset in A at which to search.
* @return A list of k-length subsets of A that sum to s.
*/
public static List<List<Integer>> subsetsWithSum(
List<Integer> A,
int k,
int s,
int o)
{
List<List<Integer>> results = new LinkedList<List<Integer>>();
if (k == 1)
{
if (A.get(o) == s)
results.add(Arrays.asList(o));
}
else
{
for (List<Integer> sub : subsetsWithSum(A, k-1, s-A.get(o), o+1))
{
List<Integer> newSub = new LinkedList<Integer>(sub);
newSub.add(0, o);
results.add(0, newSub);
}
}
if (o < A.size() - k)
results.addAll(subsetsWithSum(A, k, s, o+1));
return results;
}
现在，请注意，此解决方案通常会使用与之前调用过的相同参数集调用 subsetsWithSum(...)。因此， subsetsWithSum只是乞求被记忆。
为了记住这个函数，我将参数 k、s 和 o 放入一个三元素列表中，这将是从这些参数映射到之前计算的结果（如果有的话）的关键：
public static List<List<Integer>> subsetsWithSum(
List<Integer> A,
List<Integer> args,
Map<List<Integer>, List<List<Integer>>> cache)
{
if (cache.containsKey(args))
return cache.get(args);
int k = args.get(0), s = args.get(1), o = args.get(2);
List<List<Integer>> results = new LinkedList<List<Integer>>();
if (k == 1)
{
if (A.get(o) == s)
results.add(Arrays.asList(o));
}
else
{
List<Integer> newArgs = Arrays.asList(k-1, s-A.get(o), o+1);
for (List<Integer> sub : subsetsWithSum(A, newArgs, cache))
{
List<Integer> newSub = new LinkedList<Integer>(sub);
newSub.add(0, o);
results.add(0, newSub);
}
}
if (o < A.size() - k)
results.addAll(subsetsWithSum(A, Arrays.asList(k, s, o+1), cache));
cache.put(args, results);
return results;
}
要使用 subsetsWithSum 函数来计算总和为零的所有 k 长度子集，可以使用以下函数：
public static List<List<Integer>> subsetsWithZeroSum(List<Integer> A, int k)
{
Map<List<Integer>, List<List<Integer>>> cache =
new HashMap<List<Integer>, List<List<Integer>>> ();
return subsetsWithSum(A, Arrays.asList(k, 0, 0), cache);
}
遗憾的是，我的复杂度计算技能有点（阅读：非常）生疏，所以希望其他人可以帮助我们计算这个解决方案的时间复杂度，但这应该是对蛮力方法的改进。
编辑：为了清楚起见，请注意，上面的第一个解决方案在时间复杂度上应该等同于蛮力方法。在许多情况下，记忆函数应该会有所帮助，但在最坏的情况下，缓存永远不会包含有用的结果，并且时间复杂度将与第一个解决方案相同。另请注意，子集和问题是NP 完全的，这意味着任何解决方案都具有指数时间复杂度。结束编辑。
为了完整起见，我对此进行了测试：
public static void main(String[] args) {
List<Integer> data = Arrays.asList(9, 1, -3, -7, 5, -11);
for (List<Integer> sub : subsetsWithZeroSum(data, 4))
{
for (int i : sub)
{
System.out.print(data.get(i));
System.out.print(" ");
}
System.out.println();
}
}
它打印：
9 -3 5 -11
9 1 -3 -7