sub binhyphen2 {
    my ($str) = @_;

    my ($first, $rest) = split /-/, $str, 2;

    return $first unless defined $rest;

    my @suffixes = binhyphen2($rest);
    return map { ($first . $_, $first . '-' . $_) } @suffixes;
}

~/perl/test $ cat binhyphen.pl
#!/usr/bin/perl
use strict;
use warnings;

use Benchmark qw/cmpthese/;

my $str = $ARGV[0] || die "Usage: ./binhyphen string\n";

cmpthese (-30,
    {
        'Version 1' => sub { binhyphen1($str) },
        'Version 2' => sub { binhyphen2($str) },
    }
);

sub binhyphen1 {
    my ($str) = @_;
    my @retval;

    my $len = $str =~ tr/-//;
    my $max = (2 ** $len) - 1;
    my $pat = '^' . '([^-]*)-' x $len . '([^-]*)$';

    for my $i ( 0 .. $max ) {

       my $bits = sprintf("%03b", $i);

       my $subs = '';
       $subs .= '$' . ($_+1) . ((($bits >> $_) & 0x1) ? '-' : '')
          for (0 .. $len-1);
       $subs .= '$'.($len+1);

       my $tmp;
       eval("(\$tmp = '$str') =~ s/$pat/$subs/;");

       push @retval, $tmp;
    }
    return @retval;
}

sub binhyphen2 {
    my ($str) = @_;

    my ($first, $rest) = split /-/, $str, 2;

    return $first unless defined $rest;

    my @suffixes = binhyphen2($rest);
    return map { ($first . $_, $first . '-' . $_) } @suffixes;
}

~/perl/test $ ./binhyphen.pl a-b-c-d-e-f-g-h
            Rate Version 1 Version 2
Version 1 49.1/s        --      -99%
Version 2 4210/s     8479%        --