1

我有一个相当艰巨的任务，我觉得很难处理。

我正在尝试编写一个递归函数（根本没有循环），给定一个数组及其长度，它将打印一对子数组，每个子数组的总和将是整个数组总和的一半。换句话说，数组将被分成两组整数，使它们的和相等。

例如，给定数组 {1,2,2,0,5}，函数应输出 {1,2,2} {0,5}

我必须递归地执行它，使用一个仅获取数组本身及其大小的函数。我也只被允许使用一个额外的递归函数来解决这个问题。

任何想法或想法将不胜感激。

再一次问好！我们在课堂上有一个这样的代码

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

“ || ”运算符在递归方面是什么意思？谢谢大家！

4

2 回答 2

1

您首先计算整个数组的总和（最好是偶数），这会给您半和，您可以使用二进制背包例程来达到。

Java 中的 Stack Overflow还有一个递归实现，它与 C 并没有太大区别，并且满足您的要求。

于 2012-12-17T21:34:27.637 回答
0

从中间开始划分数组和子数组，直到只有一个元素。

将第一个元素与第二个元素进行比较，并找到这些整数的总和。

之后使用这些总和进行二进制元素比较。当做这个比较找到总和。例如，您的子数组是 {1,2} 和 {0,3}。查看第一个元素 0 和 1。当您看到小元素时，获取该子数组中的另一个元素（ {0,3} ）。之后总和现在是 3。另一部分的总和是 1 并取另一个元素 (2)。现在两者的总和都是 3。您可以将其用于所有子阵列。

我不确定解决方案。但我认为这似乎是分而治之的算法。

于 2012-12-17T21:37:51.310 回答