首先，您那里的代码似乎并没有实际工作（我在输入[1,2,3, ..., 10]上测试了它的总和3和它的输出128）。
为了让它工作，首先请注意您以非常非正统的方式实现了该算法。数学函数接受输入并产生输出。（可以说）最优雅的编程函数也应该接受输入并产生输出，因为这样我们就可以像推理数学一样推理它们。
在您的情况下，您不会产生任何输出（返回类型为void），而是将结果存储在静态变量中。这意味着很难准确说出call的含义countSubsetSum2。特别是，如果你多次调用它会发生什么？它每次都会做不同的事情（因为count变量将具有不同的起始值！）相反，如果您编写countSubsetSum2它以使其返回一个值，那么您可以将其行为定义为：返回总和为countSubsetSum2的输入的子集数。然后您可以尝试证明您的实现为何符合该规范。arr[0...k]sum
我没有做最好的解释工作，但我认为更自然的写法是：
// Algorithm stops once k is the least element in the array
if (k == 0) {
if (sum == 0 || sum == arr[k]) {
// Either we can sum to "sum"
return 1;
}
else {
// Or we can't sum to "sum"
return 0;
}
}
// Otherwise, let's recursively see if we can sum to "sum"
// Any valid subset either includes arr[k]
return countSubsetSum2(arr, k-1, sum - arr[k]) +
// Or it doesn't
countSubsetSum2(arr, k-1, sum);
如上所述，这个函数接受一个输入并输出一个我们可以定义并在数学上证明为真的值（警告：它通常不是一个证明，因为不幸的是在大多数编程语言中都有疯狂的边缘情况）。
无论如何，回到你的问题。上面代码的问题是它不存储任何数据......它只是返回计数。相反，让我们在生成它们的同时生成实际的子集。特别是，当我说Any valid subset either includes arr[k]我的意思是......我们正在生成的子集包括arr[k]; 所以添加它。下面我假设你上面写的代码是java-ish。希望这是有道理的：
// Algorithm stops once k is the least element in the array
if (k == 0) {
if (sum == 0 || sum == arr[k]) {
// Either we can sum to "sum" using just arr[0]
// So return a list of all of the subsets that sum to "sum"
// There are actually a few edge cases here, so we need to be careful
List<Set<int>> ret = new List<Set<int>>();
// First consider if the singleton containing arr[k] could equal sum
if (sum == arr[k])
{
Set<int> subSet = new Subset<int>();
subSet.Add(arr[k]);
ret.Add(subSet);
}
// Now consider the empty set
if (sum == 0)
{
Set<int> subSet = new Subset<int>();
ret.Add(subSet);
}
return ret;
}
else {
// Or we can't sum to "sum" using just arr[0]
// So return a list of all of the subsets that sum to "sum". None
// (given our inputs!)
List<Set<int>> ret = new List<Set<int>>();
return ret;
}
}
// Otherwise, let's recursively generate subsets summing to "sum"
// Any valid subset either includes arr[k]
List<Set<int>> subsetsThatNeedKthElement = genSubsetSum(arr, k-1, sum - arr[k]);
// Or it doesn't
List<Set<int>> completeSubsets = genSubsetSum(arr, k-1, sum);
// Note that subsetsThatNeedKthElement only sum to "sum" - arr[k]... so we need to add
// arr[k] to each of those subsets to create subsets which sum to "sum"
// On the other hand, completeSubsets contains subsets which already sum to "sum"
// so they're "complete"
// Initialize it with the completed subsets
List<Set<int>> ret = new List<Set<int>>(completeSubsets);
// Now augment the incomplete subsets and add them to the final list
foreach (Set<int> subset in subsetsThatNeedKthElement)
{
subset.Add(arr[k]);
ret.Add(subset);
}
return ret;
代码中的所有注释都非常混乱；但关键是这个实现总是返回它指定返回的内容（从 arr[0] 到 arr[k] 的整数集列表，总和为传入的任何总和）。
仅供参考，还有另一种方法是“自下而上”（即不使用递归），它应该更高效。如果你以这种方式实现它，那么你需要以静态状态存储额外的数据（“记忆表”）......这有点难看但很实用。但是，当您以这种方式实现它时，您需要有一种更聪明的方式来生成子集。尝试后，请随时在单独的帖子中提出该问题。