use strict;
use warnings;

use constant kMaxGroups => 6;

my @list = qw(1 1 1 2 3 4 4 4 5 5 6 6 6 7 7 8 8 8);
my $best_score = @list;
my $best_combo;
my $avgMembers = @list / kMaxGroups;
my $nominalMembers = $avgMembers;

while (my $combo = get_combo ($nominalMembers++, \@list)) {
  my $score = get_score ($avgMembers, $combo); # easy
  if ($score < $best_score) {
    $best_score = $score;
    $best_combo = $combo;
  }
}

print "Best combo score is $best_score\n";
print "@$_\n" for @$best_combo;


sub get_combo {
    my ($target, $list) = @_;
    
    return undef if $target > @$list;
    my %values;
    
    $values{$_}++ for @$list;
    
    my @groups = map {[$values{$_}, [$values{$_}, $_]]} sort keys %values;
    my $lastGroups = 0;
    
    while (@groups != $lastGroups) {
        $lastGroups = @groups;

        for my $index (0 .. $#groups - 1) {
            my $grp0members = $groups[$index][0];
            my $grp1members = $groups[$index + 1][0];
            
            next if $grp0members + $grp1members > $target;
            
            # Combine adjacent groups
            my @newGroup = (
                $grp0members + $grp1members,
                [@{$groups[$index][1]}, @{$groups[$index + 1][1]}],
                );
            
            splice @groups, $index, 2, \@newGroup;
            last;
        }
    }
    
    for my $group (@groups) {
        my @members;
    
        push @members, ($group->[1][1 + 2 * $_]) x $group->[1][2 * $_]
            for 0 .. @{$group->[1]} / 2 - 1;
        $group = \@members;
    }
    
    return \@groups;
}


sub get_score {
    my ($target, $solution) = @_;
    my $this_score = 0;

    $this_score += abs ($target - @$_) for @$solution;
    return $this_score;
}

##</code><code>##

Best combo score is 3
1 1 1
2 3
4 4 4
5 5
6 6 6
7 7
8 8 8