Backtracking and combinatronics problem in Ruby

Question

So I've been trying to solve this problem and am kinda stuck at implementing it using backtracking and would really like to understand what I'm doing wrong here. I suspect my problem is something to do with arrays being passed by reference in the methods, but can't seem to put my finger on it. Any help is appreciated. This was asked in an interview and I am trying to solve it on my own.

Here is the question:

Cards have a suite and repeating time. Given a list of cards and output size, return a list with cards that have

(all same letter or all different letters) & (all the same length or all different letter lengths).

exaple1:
input: ['X', 'Y', 'YY', 'ZZ', 'ZZZ'], 3
output: ['X', 'YY', 'ZZZ']

-------------

example2:
input: ['Y', 'Y', 'Z', 'ZZ', 'X', 'XX'], 3
output: ['Y', 'Z', 'X']

-------------

example3:
input: ['X', 'Y', 'YY', 'ZZ', 'ZZZ'], 3
output: ['X', 'YY', 'ZZZ']

My algorithm is as follows:

• call a helper method that returns if such a combo exists and the combo
• the helper method takes the list of cards and the number of cards in the output that's needed
• base case: return true and empty array if count is 0 (meaning we have no more cards to pick)
• iterate over each card
• find a combo for count - 1 cards with the current card being picked (recursively)
• if a combo is found, do checks with current card to make sure it can be added to the current combination and return
• if you've iterated over all cards and cannot find a combo, return false with empty array

  def unique_cards(cards, count)
    can, picked_cards = _unique_cards(cards, count)
    puts can ? picked_cards : false
  end

  def _unique_cards(cards, count)
    return [true, []] if count == 0
    cards.each do |card|
      card_length = card.length
      card_type = card[0]
      remaining_cards = cards - [card]
      can, selected_cards = _unique_cards(remaining_cards, count - 1)
      if can
        can_be_added = (selected_cards.all? { |c1| c1.length == card_length } || selected_cards.all? { |c1| c1[0] == card_type }) && (selected_cards.all? { |c1| c1.length != card_length   } || selected_cards.all? { |c1| c1[0] != card_type })
        if can_be_added
          selected_cards << card
          return [true, selected_cards]
        end
      end
    end
    return [false, []]
  end

Answer 1

require 'set'

def find_em(arr, n)
  arr.combination(n)
     .select do |a|
       [1, n].include?(a.map { |s| s[0] }.uniq.size) &&
       [1, n].include?(a.map(&:size).uniq.size)
      end.uniq(&:to_set)
end

find_em ['Y', 'Y', 'Z', 'ZZ', 'X', 'XX', 'Y'], 3
  #=> [["Y", "Y", "Y"], ["Y", "Z", "X"]]
find_em ['X', 'Y', 'YY', 'ZZ', 'ZZZ'], 3
  #=> [["X", "YY", "ZZZ"]]
find_em ['X', 'Y', 'YY', 'ZZ', 'ZZ'], 3
  #=> []

In the first example, without .uniq(&:to_set) we would obtain

find_em ['Y', 'Y', 'Z', 'ZZ', 'X', 'XX', 'Y'], 3
  #=> [["Y", "Y", "Y"], ["Y", "Z", "X"], ["Y", "Z", "X"], ["Z", "X", "Y"]]

See Array#combination and Array#uniq.