Not that this is going to help you, but here is naive approach using modules available from CPAN. The idea is simply to iterate through all the subsets of the values finding those which satisfy the summation constraint.

use Algorithm::Combinatorics qw(subsets);
use List::Util qw(sum);

my @data = (5, -6, 8, 10, 12, 3, 10);
my $iter = subsets(\@data);
while (my $subset = $item->next) {
  if (sum(@$subset) == 21) { print "found a solution: @$subset\n" }
}
[download]

Wow man with one sentence "Let's see... if I use the 5, then I have to form a sum of 16 with the remaining numbers. But if I don't use the 5, then... (is anything starting to click?)" you just solved the problem for me. I will try to write it in perl and post it here. Can you please explaine how you thought about this solution ? Thanks.

I'm glad that's all it took to get you going on a solution. Please post what you come up with - we'd be happy to critique it.

Recursion always involves two cases - a rather simple base case, and the recursive case.

In the base case you decide if the problem is solved. So, what really simple case can you think of where the problem is solved?

The to the recursion case: In your example the problem has a solution if the problem ((21 - 5), (-6, 8, 10, 12, 3, 10)) or the problem ((21 - (-6)), (5, 8, 10, 12, 3, 10)) or the problem ((21-8), (5, -6, 10, 12, 3, 10)) ... has a solution.

Now try to express that in perl ;-)

You need a name for the routine, say sumTo. And the args: the target and the list. So, you can write the skeleton:

sub sumTo {
    my $target = shift;
    ...
}
[download]

1. First consider the case where the list has one element that matches the target:

   sub sumTo {
       my $target = shift;
       my @list = @_;
       if( $list[ 0 ] ) == $target ) 
           return 1;
       }
       return 0;
   }
   [download]

2. Now, consider that any element of the list might exactly match the target. So you need to iterate the list and check each in turn. No need to copy the list, it's already in @_ once you've shifted off $target:

   sub sumTo {
       my $target = shift;
       for( @_ ) {
           if( $_ ) == $target ) 
               return 1;
           }
       }
       return 0;
   }
   [download]

   If the target is in the list, it returns 1, otherwise it returns 0. And if the list is empty, it also returns 0;

3. Now how to use the recursion? For each number in the list, we can subtract it from the target and remove it from the list and we then end up with a similar problem to that with which we started. So we can passed the reduced target and shortened list to the same routine and let it deal with it. If it succeeds, then we've succeeded and can return true, but we must continue iterating if otherwise.

   In order to pick out the individual values from the list, we need to use indexes rather than the values directly. We can then slice @_ to reduce the list:

   sub sumTo {
       my $target = shift;
       for( 0 .. $#_ ) {
           if( $_[ $_ ] == $target )
               return 1;
           }
           else {
               if( sumTo( $target - $_[$_], @_[0 .. $_-1, $_+1 .. $#_] ) 
   +) {
                   return 1;
               }
           }
       }
       return 0;
   }
   [download]

   And that's it. The essence of recursion is to reduce the problem at each step to a similar, but simpler problem that will eventually converge. In this case, we pick out each number in the list and subtract it from the target. We then have a smaller target and a smaller list and we recurse to solve that problem. Eventually, the list will be reduced to 1 element, and if it matches the remaining target, we've solved the problem.

   One element of the above to pay special consideration to is the slice operation which removes the current element from the list we recurse on:

   @_[0 .. $_-1, $_+1 .. $#_]
   [download]

   Understanding how that works is left as an exercise, but be sure to understand it well--write a few small programs that display the results of that expression as the index iterates--because you can guarentee if this is homework, you are going to be questioned hard about that.

There is also an error in the above, so you're gonna have to understand it to some level before you will have a working program.

First consider the case where the list has one element that matches the target:

The base case is even simpler: for $target == 0 any list fulfills the condition, so a simple return 1 if $target == 0; should do.

... and if $target < 0 no list fulfills the condition, so return 0 if $target < 0; is the second hint

Update: no, sorry, I wrongly assumed that the array containn only positive integers...

So the second hint should be return 0 if @array==0

Rule One: Do not act incautiously when confronting a little bald wrinkly smiling man.

for $target == 0 any list fulfills the condition

Que? If the target is 0 and the list 1, how does that meet the condition?

---

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.

"Science is about questioning the status quo. Questioning authority".

In the absence of evidence, opinion is indistinguishable from prejudice.

"Too many [] have been sedated by an oppressive environment of political correctness and risk aversion."

If memory serves me right, this case was presented in Higher Order Perl as the example of when NOT to use recursion, but I guess everyone needs to learn it the hard way

I'm sorry, but I really can't see an elegant way to do a scan of all possible n-ple of an array without using a recursive sub. Can you please give me a hint?

Rule One: Do not act incautiously when confronting a little bald wrinkly smiling man.

psini,
You may want to look at Finding all Combinations which has several iterator solutions (including mine). In essence, we want to find all possible combinations (powerset) minus the empty set.

Iterating over all combinations is as simple as counting. Think of all values in the array to be calculated as being 0s or 1s. If it is a 1, the value is included and if it is 0, it isn't. For instance:

5  -6  8  10  12  3  10
0  0   0  0   0   0  1 = 10
0  0   0  0   0   1  0 = 3
0  0   0  0   0   1  1 = 3, 10
0  0   0  0   1   0  0 = 12
0  0   0  0   1   0  1 = 12, 10
...
1  1   1  1   1   1  1 = 5, -6, 8, 10, 12, 3, 10
[download]

#!/usr/bin/perl
use strict;
use warnings;
use List::Util 'sum';

my @amount = (5, -6, 8, 10, 12, 3, 10);
my $count = @amount;

for (1 .. 2 ** $count - 1) {
    my @bit = split //, sprintf("%.${count}b", $_);
    my $total = sum( map {$bit[$_] ? $amount[$_] : 0 } 0 .. $#bit);
    print "$total\n";
}
[download]

Cheers - L~R

I really can't see an elegant way to do a scan of all possible n-ple of an array without using a recursive sub

Elegance for the sake of elegance is what caused the famous quote about LISP programmers who know the value of everything and the cost of nothing.

TIMTOWDI, and different algorithms will do. My point being that our OP made a very odd choice for his foray into the world of recursions. There are ways of solving this recursively without blowing up the stack, but for a beginner, this doesn't look like the best thing to start with.

Stop saying 'script'. Stop saying 'line-noise'.
We have nothing to lose but our metaphors.

Where?

In essence this problem requires that you generate the subsets of the original set. Say you have the set (1,2,3,4). You want to find all these subsets

1
1 2
1 3
1 4 
1 2 3
1 2 4
1 3 4
1 2 3 4
2
2 3
2 4
2 3 4
3
3 4
4
[download]

my @list = (1,2,3,4);
my $n = 2**@list -1;
for $b(1..$n) {
    printf "%2d: %04b ", $b, $b;
    my $i = $b;
    for (@list) {
        print "$_ " if $i%2;
        $i >>= 1;
        
    }
    print "\n";
}
__DATA__
 1: 0001 1    (get element 0)
 2: 0010 2    (get element 1)
 3: 0011 1 2  (get elements 0 and 1)
 4: 0100 3    (get element 2)
 5: 0101 1 3  (etc)
 6: 0110 2 3 
 7: 0111 1 2 3 
 8: 1000 4 
 9: 1001 1 4 
10: 1010 2 4 
11: 1011 1 2 4 
12: 1100 3 4 
13: 1101 1 3 4 
14: 1110 2 3 4 
15: 1111 1 2 3 4
[download]

Yes it works, as long as your list is short.

If the list can be longer than your integer precision, you should use big integers and I think this is overkill: there are situations in which recursion is useless and more time consuming than an iterative algorithm (I'm thinking of the classical book example of calculating n!) but in others it can be the fastest/cleanest approach

Rule One: Do not act incautiously when confronting a little bald wrinkly smiling man.

psini,
Yes it works, as long as your list is short.

Finding all possible subsets of a set is called the powerset. The number of subsets is 2 ** N - 1 where N is the number of items in the original set and the - 1 is because we do not need to consider the empty set. The number of combinations does not change regardless of what approach you use - iteration or recursion.

If the list can be longer than your integer precision, you should use big integers and I think this is overkill: there are situations in which recursion is useless and more time consuming than an iterative algorithm (I'm thinking of the classical book example of calculating n!) but in others it can be the fastest/cleanest approach

Assume the list has 20 items. That means 1,048,575 different subsets that need to be checked. Which is cleaner/faster - a single sub of about 5 lines that counts to 1,048,575 or invoking a sub a minimum of 1,048,575 times (memoization)?

Personally, I finder it harder to think in terms of recursion than iteration. There are certainly examples where a recursive solution makes more sense (Towers of Hanoi and DFS come to mind) but in this case, I still think the iterative solution is better. Have you ever tried to do a BFS using recursion - my attempts have been ugly at best.

Cheers - L~R

This problem can be expressed mathematically as

s = { sum(y) = n | y in P(x) }
[download]

That is, all you need to figure out is how to write a "power bag" function, and luckily for you several people have done that already. Try searching CPAN for "power set" for Perl versions.

lodin

http://en.wikipedia.org/wiki/Subset_sum_problem

pc88mxer has given you the pointers to solve your problem and BrowserUk an alternative, but in future you will find the Monks more receptive and more inclined to help if:-

You show some initiative on your part by posting what you have tried. It does not matter that it is not a complete solution to the entire problem or only a part.

That you have at least tried to find a solution yourself shows some commitment on your part, that you have come here to learn Perl and that you do not want just a quick fix for your Homework.

I'm wondering whether PerlMonks should have a standard netiquette message for homework submissions (I did a quick search and found nothing). Something that is provided for the student to understand what they should do to maximize his/her response. A link could be shown prominently in the document you get when you sign-up (I'm not sure how to tell Anonymous about this).

The document could be simple. Something like:

About homework: The Monks enjoy helping people solve Perl problems and this extends, modulo a few simple requests, to homework. If you're asking for homework help, you really should do the following.

• Be up-front about it. The subject should start with Homework Help:.
• Try to solve the problem yourself and show what you've done.
• Ask for hints, not a complete solution.
• Tell the monks where you're having trouble so that they know where to direct their efforts.

Following these simple guidelines will help you get the most out of your PerlMonks request and avoid the scorn heaped so heavily on those who don't.