1

I have got a pretty hard task I find difficult to handle.

I'm trying to write a recursive function (no loops at all) that, given an array and its length, will print a pair of sub arrays, each of which's sum will be half of the sum of the entire array. In other words, the array is to be divided into two groups of integers so that their sum is equal.

For example, given the array {1,2,2,0,5}, the function should output {1,2,2} {0,5}

I have to do it recursively, with a function that gets only the array itself and its size. I am also only allowed to use one more additional recursive function to solve the problem.

Any thoughts or ideas will be most appreciated.

Hello again! we got a code in class that goes like this 

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

what does the " || " operator means in terms of recursion? thanks ppl!

Tom Urkin
  • 61
  • 6

2 Answers2

1

You first calculate the sum of the whole array (it'll better be even), and this gives you the half-sum, which you can reach using a binary knapsack routine.

There is also a recursive implementation on Stack Overflow in Java, which isn't too different from C and satisfies your requirements.

Community
  • 1
  • 1
LSerni
  • 55,617
  • 10
  • 65
  • 107
0

Divide the array and sub-arrays from the middle until there is only one element.

Compare the first element with second and find sum of these integers.

After that use these sums for binary elements comparing. When doing this compare find the sum. For example your sub-arrays are {1,2} and {0,3}. Look the first elements 0 and 1. When you see the little element take the other element in that sub-array ( {0,3} ). After that sum is now 3. The other part's sum is 1 and take the other element (2). Now the sum is 3 for both. And you can use this for all sub-arrays.

I'm not sure about the solution. But I think it seems like divide-and-conquer algorithm.

Candost
  • 1,029
  • 1
  • 12
  • 28