In your code, try modifying $target to 12 and @treasures to qw(1 2 4 8 16 32). The result is that it fails to figure out that the answer is 4 + 8. (And then trips another bug on the way to reporting its wrong answer.)

This is not an incidental mistake. The fundamental problem in your approach is that you've hardcoded a finite set of patterns of inclusion/exclusion patterns that you're willing to try. With that approach the question is when, not if, your solution will break. In this case it was a pattern of inclusion that went "no, no, yes, yes" that broke. But patch that and you'll have another hole in your logic.

You can't incrementally fix your approach to get a working solution. Please don't try. If you disregard that advice, then change @treasures to qw(1 2 4 8 16 32 64 128 256 512) and try to generate every $target in the range 0..1023. For any reasonable amount of work you can do with your solution, you'll find a bug with that test.

MJD's solution, by contrast, works perfectly. How does he do that?

MJD uses recursion. As the joke goes, To understand recursion, first you must understand recursion. The joke has truth to it. The trick is that to see how recursion works for a problem of given size, you only need to understand how recursion works for all problems of smaller size. To understand, you start with examples of the smallest possible size and works your way up.

For 0 treasures, MJD's algorithm tries out [] (that's the check for $target == 0) then gives up.

For 1 treasures, MJD's algorithm tries out []. does sanity checks, makes its first recursive call and tries out [A]. then makes a second recursive call and tries out [] again (silly, isn't it?), then gives up.

For 2 treasures, MJD's algorithm tries out [], does sanity checks, then makes its first recursive call inside of which it may try out [A], [A, B], [A] then makes a second recursive call inside of which it may try out [], [B], []. Basically "empty set", followed by "all subsets with A", followed by "all subsets without A". (With some duplication due to the empty set being checked in the sanity check, then again in the second recursive call.)

For 3 or more treasures, the pattern repeats. We test the empty set. Then all subsets with the first element in the first recursive call. Then all subsets without the first element in the second recursive call (and the empty set multiple times). There is some redundancy in the checks, but we're guaranteed to actually try every subset. If the answer is to be found, we'll find it! (And if not, then we tried really, really hard.)

Hopefully this has helped you figure this case out. But that raises an interesting question. If you got through the Fibonacci and directory walk examples then you obviously understand the principle of recursion. Why would you balk on this example? My most likely guess is that you try to visualize what is happening. In the case of Fibonacci it is easy enough to verify, number by number, what is happening. In the case of a directory walk, it is easy enough to visualize what it is doing, and see how it works. But in the case of the partition problem, what we're working with is subsets of sets. That's pretty abstract. When things jump in abstraction, it is easy for our brains to get lost. Once our brains get lost, we lose track and get confused.

If that is the case for you, then focus on the concept of the size of the problem you are trying to solve. As long as all of the base cases are handled, and the recursive calls always are to "simpler" problems, the recursive algorithm will work. If the recursive calls are not to simpler problems, then you can get caught in infinite recursion.