Given 50 integers.Their sum will be less than 5*10^5. We have pick a subset from those numbers and distribute then into two arrays.The sum of integers in both array should be equal.If there are multiple solution we have to maximize the sum.If not possible report that.
Sample: 3 3 4 7 Case 1: 7 3 10 9 2 Case 2: impossible 2 21 21 Case 3: 21 9 15 15 14 24 14 3 20 23 15 Case 4: 64
Constraints: Time Limit: 4 second test cases: 100.memory limit: 32MB
Original Problem:
http://lightoj.com/volume_showproblem.php?problem=1126
I came up with a recursive idea with two states (current_position,current_absolute difference) and three choices,(I will skip number at current position,I will take it in set A,i will take it in set B). I also tried to convert it in iterative but couldn't really do it. Can anybody help me with an idea to this problem.
It seems very related to the subset sum problem; perhaps it is possible to modify the DP algorithm for existence and binary search the answer.
Yes , I know it is a subset sum problem but the time and memory limit is tight. That's why I can't think it in an efficient iterative way.
Your idea's basically correct. You want those states (possibly with memory optimization by remembering just the last 2 rows) and you want to hold in them the maximum sum of one subset. The iterative part is easy — you can consider adding the numbers into just 1 set, some with signs +, some with signs -. (I assume positive integers on the input.) The value you remember in each state is then the sum of numbers with +s. When iterating, you can try to add element a[i] as a[i] or as - a[i].