Thread: partition question

write a function called

Code:

 int partition(int arr[], int size)

which input an array of integers and decides whether
it is possible to divide the array into two groups
so the sums of both the groups will be equal.

Code:

for example arr = {1,2,2,3,5,6,1}
its could be divided into {2,2,6}  and {1,1,3,5} both of their sums is 10

so they are equal and the function needs to return 1.

the function must be recursive without loops.
you are allowed to use only one external recursive function

there are 7! (groups in this example) that needs to be tested

what is the systematic way of doing this

Also, in your example, {2,3,5} and {1,1,2,6} are also equal.

I think the solution will come down to these things:

1) If the total_sum of all #s is negative, it can't be done.
2) Else, since the total_sum is positive, you must be able to find a subset of numbers that total to total_sum/2.

You are correct. I meant ODD, not NEGATIVE. Duh me.

And I meant EVEN, not POSITIVE. Duh me again.

Originally Posted by Dino

2) Else, since the total_sum is even, you must be able to find a subset of numbers that total to total_sum/2.

You sure about that?

Code:

{ 2, 4, 8, 16, 32 }

No two subsets will have equal sums, and half of the total sum is 31, and there is no subset which sums to that, either.

I'm not sure, but I think this is an NP-complete problem. That doesn't mean it can't be solved, just that it's slow, and there is no "trick" to doing it fast.

Originally Posted by brewbuck

You sure about that?

Code:

{ 2, 4, 8, 16, 32 }

No two subsets will have equal sums, and half of the total sum is 31, and there is no subset which sums to that, either.

Well, then, that array can't be "partitioned". It passes the sum=even test, but it does not pass the "sum of some subset" == sum/2.

(edit - when I said "must", I meant you must be able to find a sum of 1/2 the total in order for the array to be partitionable - not "must" in the sense that there must always be an even split)

Originally Posted by Dino

Well, then, that array can't be "partitioned". It passes the sum=even test, but it does not pass the "sum of some subset" == sum/2.

I just don't see the usefulness of this test, because finding a subset with sum == total/2 is no different from finding a subset which sums to ANY given number. It doesn't help simplify the problem.

I think it super simplifies the problem. If the total is 20, then just find some subset that equals 10. If you can't, the array is not partitionable. If the total is -6, find some subset that equals -3.

Dino (taking the lazy man's approach to making difficult problems simple)