use List::Util 'min';
use POSIX 'ceil';
use strict;
use warnings;

sub make_ways {
    my ($N, $S, $T) = @_;

    # one coin left can we do it?
    if ($S == 1) {
        if ($T <= $N) {
            return ["$T"];
        } else {
            return 0;
        }
    }

    my $min = (2*$T-$S+$S**2)/(2*$S); ## more correctly, ceil() of this
    my $max = min( $T-(($S-1)*$S/2), $N );

    my @all_ways;
    for my $K ($min .. $max) {
        my $ways = make_ways( $K-1, $S-1, $T-$K );
        if ($ways) {
            push(@all_ways, ["$K", $ways]);
        }
    }
    if (@all_ways) {
        return \@all_ways;
    } else {
        return 0
    }
}

use Memoize;
memoize 'make_ways';

#useful for printing out details of a sane set
use Data::Dumper;
my $ways = make_ways(100, 10, 667);
#my $ways = make_ways(20, 5, 30);
#print Dumper($ways);
print_ways($ways, "", 3);

my $printed = 0;
sub print_ways {
  my ($ways, $base) = @_;

  for my $way (@$ways) {
    if (ref $way) {
      my ($coin, $more_ways) = @$way;
      my $new_base = length($base) ? "$coin+$base" : $coin;
      print_ways($more_ways, $new_base);
    } else {
      print STDERR "printed $printed\n" unless (++$printed % 1000000);
      print "$base+$way\n";
    }
  }
}