Just adding an extra cat to the bag doesn't do the trick because the grep removes both cats when the first one is used. The code needs to be reworked so that we know how many of each part there are and so that they are removed one at a time. Consider:

use strict;
use warnings;

my $target = "cowboycatdogcat";
my @partsList = qw(cow boy cat dog cat);
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]);
    }
}
[download]

Prints:

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