Here is a recursive solution. It uses the diagonal sorted in descending order but keeps track of the original order. It stops if the remaining elements become too small. I have to admit that I only looked at your one test case and that I did not do any benchmarking. 

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)] ) <= $thre
+shold; # not enough meat anymore
    if( 1==$k ) {
        push @$result, [ @$solution, $array->[$_][1] ] for grep { $arr
+ay->[$_][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;

[download]

Update: Minor improvement. The line

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

can be replaced with

push @$result, [ @$solution, $array->[$start++][1] ] while $start<$n and $array->[$start][0] > $threshold;

to avoid a few tests.

In reply to Re: Combinatorial problem by hdb
in thread Combinatorial problem by baxy77bax

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.