-1

我正在实现子集总和的算法：

SUBSET SUM(X[1 .. n], T ):
if T = 0
return T RUE
else if T < 0 or n = 0
return FALSE
else
return SUBSET SUM(X[2 .. n], T ) ∨ SUBSET SUM(X[2 .. n], T − X[1])

请帮助我在递归时如何传递简化的数组 X[2...n] ？

这是我编写的代码，它会导致分段错误：

#include <stdio.h>

    int subsetsum(int a[], int sum, int size)
    {
            if(sum==0)
            return 1;
            else if (sum<0 || size <0)
            return  0;
            else
            return (subsetsum(a+1 , sum, size-1) || subsetsum(a+1, sum - *a, size-1));
    }
    `

    int main(int argc, char **argv)
    {
            int a[]={2,4,1,3,5},x;
            x=subsetsum(a,6,5);
            printf("%d",x);
            return 0;
    }
4

2 回答 2

2 
template<class It>
void recurse(It begin, It end)
{
   ... recurse(begin+1, end) ...
}
于 2012-06-28T12:35:55.273 回答
1

当用作函数的参数时，C/C++ 中的数组被隐式衰减为指向表示数组的原始内存缓冲区的指针。因此，为了传递X[2...n]，您只需将数组指针参数递增1。例如，您可以执行以下操作：

bool subset_sum(const int* array, const int array_size, int* sum)
{
    //...your code for the rest of the algorithm

    subset_sum(array+1, array_size, sum) //one of the recursive calls
}

在下一次递归调用中传递参数array+1将使数组指针加一，并获取一个指向数组的指针X[1...n]，现在使其指向数组X[2...n]。您将使用该array_size参数来检测数组的结尾。

最后，你会这样调用subset_sum：

int array_numbers = {1, 2, 3, 4, 5, 6, 7};
int sum = 0;

subset_sum(array_numbers, sizeof(array_numbers)/sizeof(int), &sum);
于 2012-06-28T12:33:06.257 回答