o Recursive function gets a list of numbers and a target sum and solves problem:

August 1999

Perl Hardware Store

Slide #37

Recursive function gets a list of numbers and a target sum and solves problem:

# Take a list of numbers and a target # sum. return a sublist that add up to # the target, if possible, or undef
# otherwise.

         sub T {
           my ($list, $target) = @_;
           my $answer;

           if (@$list == 0) { 
             return ($target == 0) ? [] : undef 
           }

           my $first = shift @$list;

           $solution = T($list, $target); 
           unless (defined $solution) {  
             $solution = T($list, $target - $first);
             if (defined($solution)) {
               unshift @$solution, $first;
             }
           }

           # restore @$list
           unshift @$list, $first;

           return $solution;
         }