#!/usr/bin/perl

use strict;
use warnings;

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

$target = 5;
@treasures = ( 50, 2, 4, 3, 1, 2, 4, 8 );

sub find_share
{
   my ( $target, $treasures, $share, $depth ) = @_;

   $depth ||= 0; $depth += 1;
   $share ||= [];

   $calls++;

   printf qq{%-8s Calls: %-5d Depth: %-5d Share: %-10s Target: %-5d Treasures: %-16s ... },
      ( '-' x $depth ) . '>',
      $calls,
      $depth,
      "[ @$share ]",
      $target,
      "[ @$treasures ]";

   print qq{Returning "[]" because target == 0\n\n}
      and return [] if $target == 0;

   print qq{Returning undef because target < 0\n\n}
      and return undef if $target < 0;

   print qq{Returning undef because no treasures remaining\n\n}
      and return undef if @$treasures == 0;

   my ( $first, @rest ) = @$treasures;

   print qq(Putting "$first" into the share, leaving treasures [ @rest ]\n\n);

   my $solution = find_share( $target - $first, \@rest, [ @$share, $first ], $depth );

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

   print '-' x $depth, '> ',
      qq{Situation failed.  Couldn't hit target.  Omitting treasure [ $first ] and backtracking to target of $target, treasures [ @rest ] at depth $depth\n\n};

   return find_share( $target, \@rest, $share, $depth );
}

print qq<Solution: @{ find_share( $target, \@treasures ) }>;

exit;