Balancing pebbles problem

I have stumbled upon this problem before, it is a balancing problem. The program takes in an array of integers of size n. The program then determines if thi开发者_运维百科s array of integers can be split into 2 equal parts, with the sums of the integers in each half being equal.

ex. 1 2 3 8 10 4

in which, the program returns true, meaning it can be split into two halves with 14 in each

I know this is concerned with combinations/permutations and I'm not really very good at them. I've only managed to think of the brute force method. Can this be solved using any other methods? more efficient algorithms maybe?

A step by step solution will be very helpful. Thank you very much

Just giving it some really short thought:

• The problem is equivalent to finding any subset of pebbles that weighs exactly half the total pebble weight
• If the heaviest pebble weighs more than half the total pebble weight, there is no solution

This is the Partition Problem which can readily be seen to be equivalent to the Subset Sum Problem and the Knapsack Problem. It is NP-Complete, and it is thought that you can't do appreciably better than an exhaustive listing of all the combinations.

You can check all possible ways readily: For each element, it's either in the left half or the right half.

Look at my answer for this problem. Your problem is essentialy connected. You must find which sums you can achieve with the numbers. If the sum: total_sum / 2 can be achieved then you have found a solution:)