I am not sure I completely understand your problem, so maybe the following idea doesn't make sense, but, have you consider inverting the approach?

For every element make an array with the names of the sets containing it. Once that is done, you can reverse it again, converting the list of sets into a key and use it to group the elements:

# untested

my %sets = { A => [1,2,3], B => [3, 4], C => [1, 3, 4] }

my %in;

for my $set (keys %sets) {
  for my $element (@{$sets{$set}}) {
    push @{$in[$element] //= []}, $set;
  }
}

my %parts;
for my $element (keys %in) {
  my $key = join("/", sort @{$in{$element}});
  push @{$parts{$key} //= []}, $element
}

Dump \%parts;
[download]