You need only one more thing I think. And it is look-ahead assertion. Am I right, thinking, that you want match if next letter after 'cad' is 'd' or next phrase after 'namaH' is 'te'?

#!perl -l

use strict;
use warnings;

my $target = "cowboycaddog";
my @partsList = ('cowboy', 'cow', 'boy', 'cat', 'at', 'do', 'dog', 'ca
+d(?=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]);
  }
}
[download]

Update: Of course strings printed as result will include these assertions, but the problem how to remove (?=something) from output IMHO can be left as an exercise for the reader (always wanted to say that :) )