发现所有子集的总和为x - 使用初始code [英] find all subsets that sum to x - using an initial code

问题描述

我试图建立在一个问题，解决其他类似问题...下面给出的是code查找子集的总和为特定值的总数，而我试图修改$ C $Ç，这样我可以返回总结（而不是寻找计数），以该值的所有子集。

I am trying to build upon a problem, to solve another similar problem... given below is a code for finding the total number of subsets that sum to a particular value, and I am trying to modify the code so that I can return all subsets that sum to that value (instead of finding the count).

code寻找suibsets总人数的总和总和：

Code for finding the total number of suibsets that sum to 'sum':

 /**
 * 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);
}

有人能提出一些修改，这个code，使其返回子集，而不是集数？

Can someone propose some changes to this code, to make it return the subsets rather than the subset count?

推荐答案

首先，你的code是不正确的。

Firstly, your code isn't correct.

该功能，步步为营，用递归的总和排除和包括当前元素 ¹ ，移动到下一个元素，由于这些行：

The function, at every step, recurses with the sum excluding and including the current element ¹, moving on to the next element, thanks to these lines:

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

不过，再有就是还这样的：

But then there's also this:

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

这会导致它与和递归两次排除在某些情况下，当前元素（它不应该这样做）。

which causes it to recurse twice with the sum excluding the current element under some circumstances (which it should never do).

从本质上讲，你只需要删除的if语句。

Essentially you just need to remove that if-statement.

如果所有元素为正，而总和 - ARR [K-1]; 0 ，我们会继续前进，但我们永远无法得到0的总和，因为总和不能增加，因此，我们会做很多不必要的工作。因此，如果这些元素都是正的，我们可以添加一个检查如果（ARR [K - 1]; = SUM）第一个呼叫，提高了运行时间。如果这些元素并不都是积极的，在code不会找到的所有款项。

If all the elements are positive and sum - arr[k-1] < 0, we'd keep going, but we can never get a sum of 0 since the sum can't increase, thus we'd be doing a lot of unnecessary work. So, if the elements are all positive, we can add a check for if(arr[k - 1] <= sum) to the first call to improve the running time. If the elements aren't all positive, the code won't find all sums.

现在到打印的金额

如果你理解了code好，改变它打印的金额，而不是应为pretty的方便。我建议你​​工作的理解它多一点 - 跟踪什么程序会用手工做的，然后跟踪你的希望的程序做

If you understand the code well, changing it to print the sums instead should be pretty easy. I suggest you work on understanding it a bit more - trace what the program will do by hand, then trace what you want the program to do.

和暗示来解决实际的问题：在指出的是， countSubsetSum2（ARR，K-1，总和 - ARR [K-1]）; 递归与求和包括当前元素（和其他递归调用与递归的总和，不包括当前元素），你应该做的应该很清楚。

And a hint for solving the actual problem: On noting that countSubsetSum2(arr, k-1, sum - arr[k-1]); recurses with the sum including the current element (and the other recursive call recurses with the sum excluding the current element), what you should do should become clear.

1：嗯，在技术上它是相反的（我们开始与目标之和减少，而不是从0开始增加到总和为0），但同样的想法是有

1: Well, technically it's reversed (we start with the target sum and decrease to 0 instead of starting at 0 and increasing to sum), but the same idea is there.

这篇关于发现所有子集的总和为x - 使用初始code的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！