Code for dividing gifts equally
Greedy solution not correct

First, we can transform the problem as OP did by taking the difference of the book values in each pair, and then trying to split these new values in to two equal halves.  In the example of (3,5), (7,11), (8,8), (2,9), this transforms into trying to split 2 4 0 7 into equal halves, which is achieved as closely as possible with the solution [0,2,4][7].

The greedy solution attempts to place the largest unused value on the smallest pile.  In the example above, the sorted values are 7 4 2 0, and the values are placed in the following way:

    Pile 1      Pile 2
    ------      ------
     7
     7           4
     7           4,2
     7           4,2,0


leading to the correct answer.

However, consider the case of 5 5 4 3 3.  In this case, the greedy method would place the values as follows:

    Pile 1      Pile 2
    ------      ------
     5
     5           5
     5,4         5
     5,4         5,3
     5,4         5,3,3


Ending with piles of size 9 and 11, with a difference of 2.  However, the optimal solution would be piles [5,5][4,3,3] with a difference of 0.

Dynamic Programming

Instead of a greedy method, you can use a dynamic programming method to solve the problem.  The algorithm will be as follows:


Transform the initial input by taking the absolute value of the differences between each pair of books.  This is the new list of values we will use.
Sum the list of values.  Call this sum total.  We are now trying to find a subset of the values that will sum as closely to total/2 as possible (without going over).  You can convince yourself that this subset will provide us with the best answer to the problem.
Create an array of booleans of size (total/2) + 1 and initialize to false, except for element arr[0] which you initialize to true.  Each element of this array contains whether it is possible to reach a sum of that index.  For example, if in the end, arr[15] is true, then it is possible to create a subset that sums to 15.
For each element in the list of values, you traverse the array, and whenever you find arr[j] to be true, you can set arr[j+val] to be true. Note: this traversal needs to start at arr[max-val] and search towards arr[0].  If you traverse in the forwards direction, the act of setting arr[j+val] to true will cause that array element to trigger later in the loop when it shouldn't.  For example, if val were 1, the forwards loop would mistakenly set every element in the array to true.
Once step 4 is finished, your array holds all the possible subsums.  Find the largest possible subsum, and that will be the value of one pile.  Call that value largestSum.  The other pile will have value total - largestSum.  The difference will be total - 2*largestSum, which is the answer to the question.


This approach will have complexity \$O(n * m)\$, where \$n\$ is the number of book pairs and \$m\$ is the total of all the differences.  In the problem description, there are max 150 books with max value 300, so the maximum value for \$m\$ is 45000.

Compare this to the recursive solution which tries to place each value in each pile, which has complexity \$O(2^n)\$.

Sample implementation using dynamic programming

I took your program and adjusted it to use the dynamic programming approach described above.  Here is the result:

#include &lt;iostream&gt;
#include &lt;algorithm&gt;
#include &lt;cmath&gt;

int main (int argc, char const* argv[])
{
    int n;
    std::cin &gt;&gt; n;
    int difference[n];
    int total = 0;
    for(int i=0;i&lt;n;i++){
        int a,b;
        std::cin&gt;&gt;a &gt;&gt;b;
        difference[i] = std::abs(a-b);
        total += difference[i];
    }

    // Find each reachable sum up to total/2.
    int  max = total/2;
    bool arr[max+1] = { true };
    for (int i = 0; i &lt; n; i++) {
        int val = difference[i];
        for (int j = max - val; j &gt;= 0; j--) {
            if (arr[j])
                arr[j+val] = true;
        }
    }

    // Find the max reachable sum.  For that sum, print the difference between
    // one child's sum (i) and the other's (total - i).  Since i is always
    // less than or equal to (total - i), the difference will be total - i - i.
    for (int i = max; i &gt;= 0; i--) {
        if (arr[i]) {
            std::cout &lt;&lt; total - i - i &lt;&lt; std::endl;
            break;
        }
    }
    return 0;
}