use strict;
use warnings;

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

++$partsLu{$_} for @partsList;

search ($target, {%partsLu}, []);

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

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

    for my $part (keys %$partsLu) {
        next unless 0 == index $target, $part;

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

        delete $partsLu->{$part} unless --$partsLu->{$part};
        search ($remainder, {%$partsLu}, [@$used, $part]);
    }
}