The following uses a recursive search to find all matching combinations:

use strict;
use warnings;

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

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


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

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

    for my $part (@$parts) {
        next unless 0 == index $target, $part;

        my $remainder = substr $target, length $part;

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

Prints:

cow-boy-cat-dog
cowboy-cat-dog
[download]