c - 具有给定总和的整数子数组，在 C 中使用递归

Question

我有一个很难处理的任务。

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

例如，给定数组 {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);
}

“||”运算符在递归方面意味着什么？谢谢大家!

Answer 1

您首先计算整个数组的总和(最好是偶数)，这会给出一半总和，您可以使用 binary knapsack 得到它。例行公事。

还有一个recursive implementation on Stack Overflow在 Java 中，它与 C 并没有太大区别，并且可以满足您的要求。