algorithm - 找到总和为 x 的所有子集 - 使用初始代码

Question

我试图在一个问题的基础上解决另一个类似的问题...下面给出的代码用于查找总和为特定值的子集总数，我正在尝试修改代码以便我可以返回总和为该值的所有子集(而不是查找计数)。

查找总和为“sum”的 suibsets 总数的代码:

 /**
 * method to return number of sets with a given sum.
 **/
public static int count = 0;
public static void countSubsetSum2(int arr[], int k, int sum) {
    if(sum == 0) {
        count++;
        return;
    }
    if(sum != 0 && k == 0) {
        return;
    }
    if(sum < arr[k - 1]) {
        countSubsetSum2(arr, k-1, sum);
    }
    countSubsetSum2(arr, k-1, sum - arr[k-1]);
    countSubsetSum2(arr, k-1, sum);
}

有人可以建议对此代码进行一些更改，以使其返回子集而不是子集计数吗？

Answer 1

首先，您的代码不正确。

该函数在每一步都递归计算不包括和包括当前元素 ¹ 的总和，移动到下一个元素，这要归功于这些行:

countSubsetSum2(arr, k-1, sum - arr[k-1]);
countSubsetSum2(arr, k-1, sum);

但是还有这个:

if(sum < arr[k - 1]) {
    countSubsetSum2(arr, k-1, sum);
}

这导致它在某些情况下递归两次，总和不包括当前元素(它永远不应该这样做)。

本质上，您只需要删除该 if 语句。

如果所有元素都是正数且sum - arr[k-1] < 0 ，我们会继续前进，但我们永远不会得到 0 的总和，因为总和不能增加，因此我们会做很多不必要的工作。所以，如果元素都是正数，我们可以添加对 if(arr[k - 1] <= sum) 的检查。到第一次调用以改善运行时间。如果元素不都是正数，代码将不会找到所有的和。

现在打印总和

如果您很好地理解代码，将其更改为打印总和应该非常容易。我建议您进一步了解它 - 手动跟踪程序将执行的操作，然后跟踪您希望程序执行的操作。

以及解决实际问题的提示:注意到 countSubsetSum2(arr, k-1, sum - arr[k-1]);以包括当前元素的总和递归(另一个递归调用以不包括当前元素的总和递归)，你应该做什么应该变得清楚。

1:嗯，从技术上讲，它是相反的(我们从目标总和开始，然后减少到 0，而不是从 0 开始，然后增加到总和)，但这里的想法是一样的。