#!/usr/bin/perl

use strict;
use warnings;

my ( $target, @treasures, $calls );

$target = shift @ARGV || 7;
@treasures = @ARGV;
@treasures = ( 2, 3, 4, 5, 1 ) unless @treasures;

sub find_share
{
   my ( $trial_set, $avail_choices, $depth ) = @_;

   $depth ||= 0; $depth += 1;

   $calls++;

   my $ts_total = 0;

   $ts_total += $_ for @$trial_set;

   printf qq{%-8s Call %-5d Depth: %-5d Trial set: %-10s Remaining: %-16s ... },
      ( '-' x $depth ) . '>',
      $calls,
      $depth,
      "[ @$trial_set ]",
      "[ @$avail_choices ]";

   print qq{Found solution: [ @$trial_set ] == $target\n\n}
      and return $trial_set if $ts_total == $target;

   print qq{Returning undef because trial set total $ts_total > $target\n}
      and return undef if $ts_total > $target;

   print qq{Returning undef because no available choices remain } .
         qq{and $ts_total < $target\n}
            and return undef if @$avail_choices == 0;

   my ( @my_trial_set ) = @$trial_set;
   my ( @my_avail_choices ) = @$avail_choices;

   push @my_trial_set, shift @my_avail_choices;

   print qq{$ts_total < $target, so I put "$my_trial_set[-1]" } .
         qq{into the trial set, and now I'll recurse\n};

   my $solution = find_share( \@my_trial_set, \@my_avail_choices, $depth );

   print +( '-' x $depth ) . '>',
      qq(A recursive call at depth @{[ $depth + 1 ]} found that a solution } ) .
      qq(of [ @$solution ] adds up to my target of $target at depth $depth\n)
         and return [ @$solution ] if $solution;

   print '-' x $depth, '> ',
      qq{Situation failed.  Omitting treasure [ $my_trial_set[-1] ] and } .
      qq{backtracking to choices of [ @my_avail_choices ] at depth $depth\n\n};

   pop @my_trial_set;

   return find_share( \@my_trial_set, \@my_avail_choices, $depth );
}

print qq{Trying to hit target of $target...\n\n}; print <<__ANS__;

Solution: [ @{ find_share( [], \@treasures ) || [ "no solution possible" ] } ]

__ANS__

exit;

__END__

   DING!  That moment when...

    \   |   /
      _---_
  \  /     \  /
__  |       | __
     \ 8-8 /
  /   \l_l/  \
       ===
       =u=

   ...the light comes on and you get it.