#!/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; exit;