Deck of matched pairs

My game includes a deck of 50 cards. Each card within the deck is unique and has a companion card such that there are 25 “matched pairs” (like a monkey card and its companion banana card would form a matched pair). I want a way to randomize which matched pairs are used in each game such that in a 2-player game, the deck is comprised of 6 matched pairs, in a 3-player game, the deck will have 8 matched pairs, and a 4-player game includes 10 matched pairs (the remaining cards are set aside and not used for the remainder of the game). Currently, all 50 cards have common backs, and each card has the icon of its matched pair on the face (i.e., the monkey card would have a small banana icon in the corner, and the banana card would have a small monkey icon in the corner).

I have three solutions to accomplish this, and I’m looking for feedback on A) which solution is preferable, and B) other solutions I haven’t considered.

Solution 1: Shuffle All
Shuffle all 50 cards. Flip the deck faceup and set aside the top card. Scroll through the remaining cards until you find the first card’s matching pair. Then set aside the next top card and search the deck for its companion, and so on, until you have 6, 8, or 10 matched pairs (12, 16, or 20 total cards), depending on the number of players in your game. Once you have the matched pairs, shuffle these cards and deal two to each player.

Solution 2: Split Deck – Face Icons
I could have a separate “family” icon printed on the face of each card such that half of the full deck of 50 cards has the “a-icon,” and the other half would have the “b-icon.” Starting out, players would sort all 50 cards into two piles based upon their family icons – an “a” family and a “b” family. Only one family’s pile would need to be shuffled, and the top 6, 8 or 10 cards dealt, depending on the number of players. If the “a” family was shuffled and dealt, the matching pairs for all “a-icon” cards would need to be found in the “b” family pile (and vice versa).

Solution 3: Split Deck – Different Backs
The final solution I’ve considered is to, again, have an “a” and “b” deck, but this time distinguished by different color backs (blue and red for example). Shuffle the blue deck, deal out 6, 8, or 10 cards, then find the matching pairs in the red deck. The problem I have with this solution is that, when the cards selected for the game (12, 16, or 20) are shuffled together, the red/blue backs will give away which “family” the cards belong to such that it will influence whether players draw or discard during the game as they will have some level of foreknowledge they wouldn’t have had under the other two systems. (This limited foreknowledge might not be a bad thing, but I’d have to consider the strategic repercussions. Also, I’m not sure if this would affect printing costs or not, having two different backs. For those reasons, this is my least favorite solution at the moment.)

Hopefully, I’ve detailed the goals well enough to give enough information for constructive feedback. Please let me know your thoughts.

Thanks,
Tom