First turn on strictures (you always use strictures don't you?), then set up the target string and the search list. Perform the search using the starting parameters.

use strict;
use warnings;

my $target = "cowboycatdog";
my @parts = qw(cow cowboy boy cat at do dog);

search ($target, [@parts], []);
[download]

Assign the parameters passed to the sub to local variables. Note that the arrays are passed as references so that two arrays can be passed.

sub search {
    my ($target, $parts, $used) = @_;
[download]

Check to see if there is anything left to match. If the target string is zero length then we have a successful combination in @$used. Print the result and return.

    unless (length $target) {
        print join ("-", @$used), "\n";
        return;
    }
[download]

otherwise loop over the remaining unused words looking for matches with the start of the remaining target string.

    for my $part (@$parts) {
[download]

if there is no match for the current word at the start of the target string skip to the next word

        next unless 0 == index $target, $part;
[download]

otherwise isolate the part of the target string following the current word.

        my $remainder = substr $target, length $part;
[download]

Recursively search the remaining part of the target string using the word list passed in excluding the current word and passing a list of the words used so far plus the current word.

        search ($remainder, [grep {$part ne $_} @$parts], [@$used, $pa
+rt]);
    }
}
[download]