use strict;
use warnings;
use List::Util qw/ sum min /;

sub find {
    my( $array, $n, $k, $threshold, $start, $solution, $result ) = @_;
    return if sum( @{$array}[$start..min($start+$k-1,$n-1)] ) <= $threshold; # not enough meat anymore
    if( 1==$k ) {
        push @$result, [ @$solution, $array->[$_][1] ] for grep { $array->[$_][0] > $threshold } $start..$n-1;
    } else {
        find( $array, $n, $k-1, $threshold-$array->[$_][0], $_+1, [ @$solution, $array->[$_][1] ], $result ) for $start..$n-$k;
    }
}

my $MTX = [
	   [4,-1,-2,-2, 0,-1],
	   [-1,5, 0, 2,-3, 1],
	   [-2,0, 6, 1,-3, 5],
	   [-2,2, 1, 7,-3, 0],
	   [0,-3,-3,-3, 8,-3],
	   [-1,1, 5, 0,-3, 9],
	  ];

my $k = 3;
my $threshold = 17;

my $n = @$MTX;
my @diag = sort {$b->[0]<=>$a->[0]} map { [$MTX->[$_][$_],$_] } 0..$n-1;
my @result;
find( \@diag, $n, $k, $threshold, 0, [], \@result );

print "@$_: ".sum(map{$MTX->[$_][$_]}@$_)."\n" for @result;

##</code><code>##

push @$result, [ @$solution, $array->[$_][1] ] for grep { $array->[$_][0] > $threshold } $start..$n-1;