Choose One item from each Set without Duplication -- find all Solutions

A programmatic version (only realistic for small datasets) could be to invert the mappings, generate all combinations and ensuring we have a set of size 5:

d = {'A': {1, 2, 3, 4, 5},
     'B': {1, 2, 4},
     'C': {2, 3, 5},
     'D': {1, 3, 4, 5},
     'E': {3, 4}}

from collections import defaultdict
from itertools import product

d2 = defaultdict(set)
for k, s in d.items():
    for v in s:
        d2[v].add(k)
# {1: {'A', 'B', 'D'},
#  2: {'A', 'B', 'C'},
#  3: {'A', 'C', 'D', 'E'},
#  4: {'A', 'B', 'D', 'E'},
#  5: {'A', 'C', 'D'}}

out = [x for x in product(*d2.values()) if len(set(x))==len(d2)]

output:

[('A', 'C', 'E', 'B', 'D'),
 ('A', 'B', 'E', 'D', 'C'),
 ('A', 'B', 'D', 'E', 'C'),
 ('A', 'B', 'C', 'E', 'D'),
 ('D', 'A', 'E', 'B', 'C'),
 ('D', 'C', 'E', 'B', 'A'),
 ('D', 'B', 'E', 'A', 'C'),
 ('D', 'B', 'A', 'E', 'C'),
 ('D', 'B', 'C', 'E', 'A'),
 ('B', 'A', 'E', 'D', 'C'),
 ('B', 'A', 'D', 'E', 'C'),
 ('B', 'A', 'C', 'E', 'D'),
 ('B', 'C', 'E', 'A', 'D'),
 ('B', 'C', 'E', 'D', 'A'),
 ('B', 'C', 'D', 'E', 'A'),
 ('B', 'C', 'A', 'E', 'D')]

Firstly, it is worth to mention that the term combinations isn't applicable here.

Combination is a selection of items from a set that has distinct members

And permutations represent different ways of arranging elements of a combination.

The key point, is that combination is selection done on a single source of data. Meanwhile, we have multiple Sets.

And if you pay attention to the result, which sample data provided in the question is expected to give, you'll find out that all these "combinations" consist of exactly the same elements 1,2,3,4,5 (because you've used only these numbers in all the sets), but combinations can't be comprised of completely identical elements.

The sequences that need to be generated are rather similar to Cartesian product, with one caveat: we need to discard some of them because of uniqueness requirement. So this term might not be suitable either. Hence, I will call them samples.

We can address the problem in the following steps:

• Create a Queue that will contain all the resulting samples. Each sample would be represented by a Set.
• Add the first empty sample to the queue.
• Iterate over the given Collection of Sets and for every set based on the existing sample in the queue generate new samples containing all the elements from a current set that were not present previously. If there are no such elements, sample should be discarded.

Implementation might look like that:

public static Queue<Set<Integer>> findSamples(List<Set<Integer>> sets) {
    
    Queue<Set<Integer>> samples = new ArrayDeque<>(); // queue of samples
    samples.add(Collections.emptySet());              // the fist empty sample
    
    for (Set<Integer> set : sets) {
        Queue<Set<Integer>> updated = new ArrayDeque<>(); // updated samples removed from the queue would be accumulated here
        
        while (!samples.isEmpty()) {
            Set<Integer> sample = samples.remove();
            updated.addAll(tryAdd(sample, set));
        }
        
        samples = updated;
    }
    
    return samples;
}

public static List<Set<Integer>> tryAdd(Set<Integer> sample, Set<Integer> set) {
    List<Set<Integer>> newSamples = new ArrayList<>();
    
    for (Integer next : set) {
        if (sample.contains(next)) continue;
        
        Set<Integer> copy = new LinkedHashSet<>(sample); // NB: HashSet would be sufficient here, LinkedHashSet is used ONLY for demonstration purposes
        copy.add(next);
        newSamples.add(copy);
    }
    return newSamples;
}

main()

public static void main(String[] args) {
    List<Set<Integer>> sets = List.of(
        Set.of(1, 2, 3, 4, 5),
        Set.of(1, 2, 4),
        Set.of(2, 3, 5),
        Set.of(1, 3, 4, 5),
        Set.of(3, 4)
    );
    
    findSamples(sets)
        .forEach(System.out::println); // printing the result
}

Output:

[1, 4, 2, 5, 3]
[1, 2, 5, 4, 3]
[1, 2, 5, 3, 4]
[1, 2, 3, 5, 4]
[5, 4, 2, 1, 3]
[5, 2, 3, 1, 4]
[5, 1, 2, 4, 3]
[5, 1, 2, 3, 4]
[4, 2, 5, 1, 3]
[4, 1, 2, 5, 3]
[3, 2, 5, 1, 4]
[3, 1, 2, 5, 4]
[2, 4, 5, 1, 3]
[2, 1, 5, 4, 3]
[2, 1, 5, 3, 4]
[2, 1, 3, 5, 4]