Could you clarify? You say the string is of the form "letter + weight", but I'm not sure how to parse the string in that sense. In "a?1", is "a" the letter and "1" the weight? If so, what role does "?" play?

Based on the example $str and $substring, I'll treat the first two characters as a notional "token", and say that elements actually consist of a two-character token followed by the numeric weight.

It appears the elements are unique, but neither tokens nor weights have to be.

The $substring appears to list tokens, and my guess is that by "contained within" you mean that each of the listed tokens must appear as an element of a qualifying combination. Since "substring" usually implies both ordered and consecutive, I've renamed it to $subset below.

It is not clear whether a qualifying combination can have repeated tokens. For example is (c?6, b%5, a?2, a?1)a valid combination? I've assumed below that it is valid.

Since I've assumed order is not relevant to the qualification criteria, it seems that placing the largest weight first is simply a display requirement.

Based on those assumptions, here's an attempt at some code:

use strict;
use warnings;
use Math::Combinatorics;
use List::Util qw{ all };

my $firstLetter = 'c';
my $str = 'a?1,a?2,a%3,b?2,b?3,b%5,c%4,c%5,c?6,d%2';
my $subset = 'a?,b%,c?';

print display($_, $firstLetter), "\n"
  for grep qualify($_, $subset),
    Math::Combinatorics::combine(4,split ",",$str);

sub qualify {
  my($combo, $subset) = @_;

  # Check if numbers are all unique, using the "postincrement" trick
  my %seen;
  $seen{$_}++ or return 0 for map substr($_, 2), @$combo;

  # Find all the tokens in the combo. If all the ones we need in the
  # subset are represented, we're good.
  my %token = map +(substr($_, 0, 2) => 1), @$combo;
  return all { $token{$_} } split /,/, $subset;
}

sub display {
  my($combo, $first) = @_;
  # Use a Schwartzian transform over a reverse sort on our
  # calculated "firstness weight": -1 for elements with the wrong
  # first letter, else the element's weight. sort() is overkill here,
  # I'd use a different approach if we were considering larger sets.
  return join ',',
    map $_->[0],
      sort { $b->[1] <=> $a->[1] }
        map [ $_, substr($_, 0, 1) eq $first ? substr($_, 2) : -1 ],
          @$combo;
}
[download]

This outputs:

c?6,a?1,a?2,b%5
c?6,a?1,a%3,b%5
c?6,a?1,b?2,b%5
c?6,a?1,b?3,b%5
c?6,c%4,a?1,b%5
c?6,a?1,b%5,d%2
c?6,a?2,a%3,b%5
c?6,a?2,b?3,b%5
c?6,c%4,a?2,b%5
[download]

Does that look like the sort of thing you want?