Algorithm

There's a n-element array of integers- 1 or 2.
We have to find subsequence which sum equals x.
How to do that ? I have no fucking idea.
Inb4 bruteforce

/cygdrive/b $ time sh -c "perl sum.pl 56409 < file.txt"
0..37670

real    0m1.931s
user    0m0.000s
sys     0m0.092s
/cygdrive/b $ perl -e "for(0..1000000){print 1+int(2*rand)}">file.txt
/cygdrive/b $ ls -l file.txt
-rwx------+ 1 Administrators None 1000001 2010-10-22 11:37 file.txt
/cygdrive/b $ time sh -c "perl sum.pl 56409 < file.txt"
0..37484

real    0m1.843s
user    0m0.015s
sys     0m0.047s
/cygdrive/b $ echo 2`cat file.txt` > file.txt
/cygdrive/b $ time sh -c "perl sum.pl 56409 < file.txt"
1..37485

real    0m1.893s
user    0m0.015s
sys     0m0.061s
/cygdrive/b $ cat sum.pl
use strict;

my $target=shift;
my @values=split //,<>;

my $sum=0;

my $left=0;
my $right=0;

while($right<=@values){
        if($sum<$target){
                $sum+=$values[$right];
                $right++;
        } elsif($sum>$target){
                $sum-=$values[$left];
                $left++;
        } else{
                print "$left..$right\n";

                exit;
        }
}

print "No solution\n";
/cygdrive/b $

It would be times faster in C.