c - C 中的递归函数(2 个子数组)

Question

我们的类中有一段代码，如下所示:

int SubsetSum(int arr[], int idx, int n, int S)
{
    if (S == 0)
        return 1; // This is stopping condition #1.

    if (S < 0 || n == 0)
        return 0; // This is stopping condition #2.

    return SubsetSum(arr, idx + 1, n - 1, S - arr[idx])
        || SubsetSum(arr, idx + 1, n - 1, S);
}

如果数组可以分为两个总和相等(即数组之和/2)的子数组，则此代码返回 1。我想扩展这个函数，以便它返回两个带有数字的数组。

对于 1,2,2,3,0 的输入，它应该返回: 到达1:2,2 arr2:3,1

我怎样才能做到这一点？我不能使用循环，只能使用递归函数。

Answer 1

你的前提不正确:你写了

This code returns 1 if the array can be divided into two subarrays with equal sum.

这不是真的。测试

int main() {
   int a[5];
   a[0] = 1; a[1] = 0; a[2] = 0; a[3] = 0; a[4] = 0;

   int const r1 = SubsetSum(a, 0, 5, 1);
   printf("%d\n", r1);

   return 0;
}

这会返回“1” - 即使它不能划分为总和相等的子数组。

请考虑您的代码并准确描述您想要的内容。