use strict;
use warnings;
use Data::Dump qw/pp dd/;
use Data::Dumper;


# --- input
my @input  = (1,99,2,40,50,60,90,3,5,95,100);
my $target = 100;

my %steps = ( 0 => []);


# --- processing
my @deltas = sort { $a <=> $b } @input ;
for my $delta ( @deltas ) {
    for my $last (keys %steps) {
        my $next = $last + $delta;
        unshift @{$steps{$next}},$last
          if $next <= $target-$delta    # $delta grows!
            or $next == $target;        # goal
    }
#    pp $delta, \%steps;
}

pp \%steps;


# --- output
my %free;
$free{$_}++ for @deltas;

our $level = -1;

sub walk_back {
    my ($target,$h_path)=@_;
    local $level = $level +1;
    for my $last (@{$steps{$target}}) {
        my $delta = $target-$last;
        next unless $free{$delta};
        local $free{$delta} = $free{$delta}-1;
        print "\t" x $level , "+$delta\n";
        my $sub_path = $h_path->{$delta} = {};
        if ( $last>0 ) {
            walk_back($last,$sub_path)
        } else {
            print "\n\n";
        }
    }
}

my %path;

walk_back($target,\%path);
pp \@deltas;
print Dumper \%path;