I have a collection of sets S[i], I need to pick C[i] items from each correspoinding set. Some items might belong to several sets at once, picking the same item twice is not allowed.
Here's an example to explain better:
Set #1 [b, c, d, e], pick 2
Set #2 [a, b, c], pick 2
Set #3 [w, x, y, z], pick 1
Set #4 [a, d, e], pick 1
One of the solutions would be:
Set #1 [b, d]
Set #2 [a, c]
Set #3 [x]
Set #4 [e]
I don't need to find all possible solutions, just any one that satisfies the conditions above.
My question is: is there a better approach other than bruteforcing all possible combinations until I find one? Obviously, greedy algorithm won't work (picking [b, c] for set #1 will make it impossible to pick 2 items from set #2). Do any other options exist? Is my problem equivalent to some well-known problem?
If brute force is the only option, what's the best way to implement it to avoid going down dead-ends? E.g. if I pick:
Set #1 [b, e]
Set #2 [a, d]
it would be useless to try all possible combinations for set #3 since picking anyting from set #4 is already impossible.