#!perl -l

use strict;
use warnings;

my $target = "cowboycaddog";
my @partsList = ('cowboy', 'cow', 'boy', 'cat', 'at', 'do', 'dog', 'cad(?=d)');
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)
  {
    my $tmp = $target;
    my $re = qr/$part/;
    next unless $tmp=~s/^$re//;

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