Cards Game - Subset Sum - Can the following algorithm be optimized?

Question

Ok, the cards game I'm developing is pretty similar to Scopa if someone knows it. The deck contains 40 cards divided into 4 different suits of 10 cards each (ace => value 1, two => value 2, three = ..., four, five, six, seven, knave, queen, king => value 10). There are 2 players (actually an AI and a human player) and they have 4 cards in their hand.

There are 4 free cards to take on the table and players can take them only respecting the following rules: 1) Court cards (knave, queen and king) can only take identical court cards (for example, if I have a queen I can only take a queen from the table). 2) Numeric cards (from ace to seven) can take identical numeric cards or smaller numeric cards by sum (for example, if I have a seven I can take a seven or { an ace, a six } or {a three, a four } or { an ace, three two }).

Now the time has come to find which cards the AI can eventually take during it's turn:

    private List<List<Card>> CalculateAITake()
    {
        List<Int32> handValues = new List<Int32>();
        List<List<Card>> takes = new List<List<Card>>();

        /* here i take every hand card value, in a unique way
         * in order to avoid processing two or more times the
         * same value
         */
        foreach (Card card in m_AIHand)
        {
            Int32 cardValue = (Int32)card.Rank;

            if (!handValues.Contains(cardValue))
                handValues.Add(cardValue);
        }

        /* for each hand card value now, I calculate the
         * combinations of cards I can take from table
         */
        foreach (Int32 handValue in handValues)
        {
            // it's a court card, let's use a direct and faster approach
            if (handValue >= 8)
            {
                foreach (Card card in m_CardsOnTable)
                {
                    if ((Int32)card.Rank == handValue)
                    {
                        List<Card> take = new List<Card>();
                        take.Add(card);

                        takes.Add(take);
                    }
                }
            }
            else 
                // it's a numeric card, let's use recursion
                CalculateAITakeRecursion(takes, (new List<Card>(m_CardsOnTable)), 0, (new List<Card>()), handValue, 0);
        }

        return takes;
    }

    private void CalculateAITakeRecursion(List<List<Card>> takes, List<Card> cardsExcluded, Int32 cardsExcludedIndex, List<Card> cardsIncluded, Int32 sumWanted, Int32 sumPartial)
    {
        for (Int32 i = cardsExcludedIndex; i < cardsExcluded.Count; ++i)
        {
            Card cardExcluded = cardsExcluded[i];
            Int32 sumCurrent = sumPartial + (Int32)cardExcluded.Rank;

            /* the current sum is lesser than the hand card value
             * so I keep on recursing
             */
            if (sumCurrent < sumWanted)
            {
                List<Card> cardsExcludedCopy = new List<Card>(cardsExcluded);
                cardsExcludedCopy.Remove(cardExcluded);

                List<Card> cardsIncludedCopy = new List<Card>(cardsIncluded);
                cardsIncludedCopy.Add(cardExcluded);

                CalculateAITakeRecursion(takes, cardsExcludedCopy, ++cardsExcludedIndex, cardsIncludedCopy, sumWanted, sumCurrent);
            }
            /* the current sum is equal to the hand card value
             * we have a new valid combination!
             */
            else if (sumCurrent == sumWanted)
            {
                cardsIncluded.Add(cardExcluded);

                Boolean newTakeIsUnique = true;
                Int32 newTakeCount = cardsIncluded.Count;

                /* problem: sometimes in my results i can find both
                 * { ace of hearts, two of spades }
                 * { two of spades, ace of hearts }
                 * not good, I don't want it to happens because there
                 * is still a lot of work to do on those results!
                 * Contains() is not enought to guarantee unique results
                 * so I have to do this!
                 */
                foreach (List<Card> take in takes)
                {
                    if (take.Count == newTakeCount)
                    {
                        Int32 matchesCount = 0;

                        foreach (Card card in take)
                        {
                            if (cardsIncluded.Contains(card))
                                matchesCount++;      
                        }

                        if (newTakeCount == matchesCount)
                        {
                            newTakeIsUnique = false;
                            break;
                        }
                    }
                }

                if (newTakeIsUnique)
                    takes.Add(cardsIncluded);
            }
        }
    }

Do you think that this algorithm could be improved somehow? I'm trying to shorten this code as much as I can so that it can be easy to debug and easy to maintain... also, if someone has a more elegant solution to avoid duplicate combinations I would really, really appreciate it (I don't want to get both { ace of hearts, two of spades } and { two of spades, ace of hearts }... only one of them).

Many, many thanks in advance!

Answer 1

Rather than considering each numeric card in your hand and looking for free cards that total it, I would consider each possible total of free cards and looking for a numeric card in your hand that matches it. You could use some sort of bitset to speed up the check for a matching card in your hand, and if you sort the free cards in ascending order, you could avoid adding a card matching one that you skipped, and you could stop adding cards if you exceeded the highest numeric card in your hand.

EDIT: pseudocode follows (sorry, I'm no good at naming variables):

call find_subset_sum(1, List<int>, 0)
// Passing the total because it's easy to calculate as we go
sub find_subset_sum(int value, List<int> play, total)
  if total > max_hand_card
    return // trying to pick up too many cards
  if total in hand_set
    call store_play(play)
  if value > max_free_card
    return // no more cards available to pick up
  // try picking up higher value cards only
  find_subset_sum(value + 1, play, total)
  // now try picking up cards of this value
  for each free card
    if card value = value // only consider cards of this value
      total += value
      play.append(card)
      find_subset_sum(value + 1, play, total)
  // you could remove all the added cards here
  // this would avoid having to copy the list each time
  // you could then also move the first recursive call here too

It looks a bit odd but that's to ensure that if you only need one card of a particular value you don't unnecessarily consider picking up each available card of that value.

You can optimise this still further by sorting the array in ascending order.