Task — Tug of war

You are given a set of $n integers ($n1, n2, n3, ….). Write a script to divide the set in two subsets of $n / 2 sizes each so that the difference of the sum of the two subsets is the least. If $n is even then each subset must be of size $n / 2. If $n is odd then the size of one subset must be ($n - 1)/2 and other must be ($n + 1)/2.

Examples

Example 1:
Input:        Set = (10, 20, 30, 40, 50, 60, 70, 80, 
                     90, 100)
Output:  Subset 1 = (30, 40, 60, 70, 80)
         Subset 2 = (10, 20, 50, 90, 100)

Example 2:
Input:        Set = (10, -15, 20, 30, -25, 0, 5, 40, -5)
Output:  Subset 1 = (30, 0, 5, -5)
         Subset 2 = (10, -15, 20, -25, 40)

Analysis

The algorithm I adopted is to find a subset of the input numbers with a size of of $n / 2 (or ($n - 1)/2) which sums as close as possible to half the sum of the input set (the 'target'). The remaining subset will then sum to a value the same distance from the other side of the target, and thus these are the desired pair of subsets.

I use Algorithm::Combinatorics to find all the possible subsets of $n of the appropriate length, and check to see which sums closest to the target. If the distance is zero I can drop out of the search.

To get the other subset I join the members of $n into a string separated by '!', then use repeated applications of $string =~ s/!$i!/!/; to delete the numbers in the first subset, and then split the string to yield the desired other subset.

Try it 

#!/usr/bin/perl

# Peter Campbell Smith : 2021-08-02

use utf8;
use v5.26;
use warnings;
binmode STDOUT, ':utf8';
use Algorithm::Combinatorics qw(combinations);

my (@tests, $test);

@tests = ([10, 20, 30, 40, 50, 60, 70, 80, 90, 100],
    [10, -15, 20, 30, -25, 0, 5, 40, -5],
    [18, 25, 7, 39, 11, 17, 22, 1 ,41, 19, -5],
    [23, 67, 43, 96, 23, 14, 85, -300, 43, 20, 87, 99, 0, 35, 21, 77, 88, 77, 54, 70, 34, 56, 500]);
    
for $test (@tests) {
    tug_of_war($test);
}

sub tug_of_war {

    my (@in, @out1, @out2, $target, $count, $subcount, $best, $set, $c, $total, $gap, $i, $string);
    
    # some useful numbers
    @in = @{$_[0]};
    $target = total(@in) / 2;       # target value for each subset to add up to (half the total of the input numbers)
    $count = scalar @in;            # number of numbers
    $subcount = int($count / 2);    # number in each (or the smaller) subset

    # look for subset that is closest to the target
    $best = 1e10;       # the closest gap found so far between the chosen combination and the target.

    # iterate over all possible combinations of the first $subcount numbers
    $set = combinations(\@in, $subcount);   
    while ($c = $set->next) {
        $total = total(@$c);           # total of this combination
        $gap = int($total - $target);  # gap between that and the target
        if (abs($gap) < $best) {       # is it the best so far?
            @out1 = @$c;
            $best = abs($gap);
            last if $best == 0;
        }
    }

    # get the other subset
    $string = '!' . join('!', @in) . '!';   # make the input set into a string like !11!22!33!
    for $i (@out1) {
        $string =~ s/!$i!/!/;   # remove each one which is in the first subset
    }
    @out2 = split /!/, substr($string, 1);   # split the string back into an array

    # print the results
    say qq[\nInput:        Set = (] . join(', ', @in) . qq[) Σ = ] . total(@in);
    say qq[Output:  Subset 1 = (] . join(', ', @out1) . qq[) Σ = ] . total(@out1);
    say qq[         Subset 2 = (] . join(', ', @out2) . qq[) Σ = ] . total(@out2);
}

sub total {    # total(@x) returns sum of all the elements
    
    my ($i, $sum);
    for $i (@_) { $sum += $i; }
    return $sum;
}

Output

Input:        Set = (10, 20, 30, 40, 50, 60, 70, 80, 90, 100) Σ = 550
Output:  Subset 1 = (10, 20, 50, 90, 100) Σ = 270
         Subset 2 = (30, 40, 60, 70, 80) Σ = 280

Input:        Set = (10, -15, 20, 30, -25, 0, 5, 40, -5) Σ = 60
Output:  Subset 1 = (10, -15, 30, 5) Σ = 30
         Subset 2 = (20, -25, 0, 40, -5) Σ = 30

Input:        Set = (18, 25, 7, 39, 11, 17, 22, 1, 41, 19, -5) Σ = 195
Output:  Subset 1 = (18, 25, 41, 19, -5) Σ = 98
         Subset 2 = (7, 39, 11, 17, 22, 1) Σ = 97

Input:        Set = (23, 67, 43, 96, 23, 14, 85, -300, 43, 20, 87, 99, 0, 35, 21, 77, 88, 77, 54, 70, 34, 56, 500) Σ = 1312
Output:  Subset 1 = (23, 67, 43, 96, 23, 14, 85, -300, 35, 70, 500) Σ = 656
         Subset 2 = (43, 20, 87, 99, 0, 21, 77, 88, 77, 54, 34, 56) Σ = 656