use strict;
use warnings;

use Algorithm::Loops qw( NestedLoops );
use List::Util       qw( sum );

my $M = 15;
my $N = 4;

my @groups;

sub init_groups {
   my $iter = NestedLoops(
      [  [ 1..$M-($N-1) ],
         ( sub {
            my $s = sum(@_);
            my $n = @_;
            [ $_..$M-$s-(($N-1)-$n) ]
         } ) x ($N-2),
         sub {
            my $rest = $M-sum(@_);
            $rest >= $_ ? [$rest] : []
         },
      ],
   );

   while (my @group = $iter->()) {
      push @groups, \@group;
   }
}

sub find_groups {
   local our %left; ++$left{$_} for grep $_ <= ($M-$N+1), @_;

   my @solutions;

   local *helper = sub {
      my $leaf = 1;
      my $first_idx = $_[-1] || 0;
      GROUP: for my $group_idx ($first_idx..$#groups) {
         local %left = %left;
         for my $x (@{$groups[$group_idx]}) {
            next GROUP if --$left{$x} < 0;
         }
         $leaf = 0;
         local $_[@_] = $group_idx;
         &helper;
      }

      push @solutions, [ @_ ] if $leaf;
   };

   helper();
   return \@solutions;
}

{
   init_groups();

   my @input = @ARGV ? @ARGV : ( sort { $a <=> $b } map int(rand(15))+1, 1..50 );
   print(join(' ', @input), "\n");

   my $solutions = find_groups(@input);
   for my $solution (@$solutions) {
      my $sep = '';
      for my $group_idx (@$solution) {
         print($sep, join(',', @{ $groups[$group_idx] }));
         $sep = ' | ';
      }
      print("\n");
   }
}