use strict;
use warnings;

use Algorithm::Loops 'NestedLoops';

use List::Util qw'sum min';

# find all subsets of 1..$N of size $S whose sum is $T:

sub selections {
  my ($N, $S, $T, $callback) = @_;
  NestedLoops(
    [
       (sub {
          no warnings 'uninitialized';
          my $new_t = $T - sum(@_); # Target sum for remaining dials
          my $new_s = $S - @_;      # Number of remaining dials
          # Each dial is > than the one to the left of it
          my $min = $_[-1] + 1;
          # The value must be large enough that the remaining dials
          # can reach the target. The min formula is
my @min_vals = map $N-$_, reverse 1..$new_s-1;
my $s = sum @min_vals;
my $x = $new_t - $s;

          if ($x > $min) { $min = $x }
          my $max = $N - $new_s;
          # The value must be small enough that the remaining dials
          # can all increase and still not overshoot the target. The
          # max formula is
          # x + (x + 1) + ... + (x + S-1) = new_t
          # ==> (x * S) + ((S-1)*S/2)
          # Solving for x:
          $x =int( ($new_t - (($new_s - 1) * $new_s/2))/$new_s );
          if ($x < $max) { $max = $x }

          [$min .. $max]
        }) x $S
    ],
  );
}

my $i = selections(100, 10, 667);
my $solution_count = 0;
while ($i->()) {
  ++$solution_count;
  print "$solution_count iterations\n" if $solution_count % 10_000 == 0;
}