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]