Nope, that code is only memoized for generation, the output stage is unmemoized and hence very slow.

The semi-memoized output code is in my followup. Here's the whole thing joined up and ready to run.

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 thi
+s
    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';

my $ways = make_ways(100, 10, 667);
my $printed = 0;
nasty_print_ways($ways, "", 6);
print "$printed\n";

# do my own memoizing as I couldn't get Memoize to work, for this func
+tion
# possibly to do with the arguments being array refs
my %strings;
sub string_ways {
  my $ways = $_[0];

  if (my $strings = $strings{$ways})
  {
    #die "already $strings";
    return $strings
  }
  my @strings;
  for my $way (@$ways) {
    if (ref $way) {
      my ($coin, $more_ways) = @$way;
      push(@strings, map {"$_+$coin"} (@{string_ways($more_ways)}));
    } else {
      push(@strings, $way);
    }
  }

  return $strings{$ways} = \@strings;
}

sub nasty_print_ways {
  my ($ways, $base, $depth) = @_;

  if ($depth == 0) {
      my $strings = string_ways($ways);
      for my $string (@$strings) {
          $printed++;
          #print STDERR "$printed\n" unless ($printed % 10000000);
          #print "$string+$base\n";
        }
  }
  else {
    $depth--;
    for my $way (@$ways) {
      if (ref $way) {
        my ($coin, $more_ways) = @$way;
        my $new_base = length($base) ? "$coin+$base" : $coin;
        nasty_print_ways($more_ways, $new_base, $depth);
      } else {
        # print "$base+$way\n";
      }
    }
  }
}
[download]

The reason I wanted you to run blokheads quick code was to be able to get a quick comparison of my machine and your machine. It's not important.

I ran your C and it took 2 or 3 hours. I'm running it again with your optimisations, although that fomit-pointer (or whatever it was) make my gcc complain.

By the way, your code printed out -114xxx. That's because j is a double (a kind of float) and you format is "%d" but %d is for int. I've changed j to unsigned long long int and printf("%lld", j). I'm waiting for it to complete.