給定總和的整數子陣列，使用遞歸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); 
} 

什麼是「||」運營商遞歸而言意味着什麼？ 感謝ppl！

Answer 1

你首先計算整個數組的總和（它最好是），這給你半和數，你可以使用binary knapsack例程來達到。

Java中還有一個recursive implementation on Stack Overflow，它與C沒有太大區別，可以滿足您的要求。

Answer 2

從中間劃分數組和子數組，直到只有一個元素。

將第一個元素與第二個元素進行比較，找出這些整數的總和。

之後，使用這些和進行二進制元素比較。當做這個比較找到總和。例如，您的子數組是{1,2}和{0,3}。查看第一個元素0和1.當您看到該小元素時，將該子數組中的其他元素（{0,3}）。之後，現在的總和是3.另一部分的總和是1並且取另一個元素（2）。現在兩者的總和都是3。你可以用它來做所有的子數組。

我不確定解決方案。但我認爲這似乎是分而治之的算法。