Performance/Optimization of Knapsack(ish) algorithm for move generation for a game

I'm writing an AI for an italian Card game scopa http://en.wikipedia.org/wiki/Scopa And as part of it i need to generate all moves available to the user.

A move consists of finding cards in the centerboard that sum to a card in the players hand.

For example if I have a 5 in my hand and the center contains a [5,4,3,2,1,2] the possible moves would be:

pick up the 5 with my five

pick up the 4 and 1 with my five

pick up one of the twos and the three with my five

pick up the other tow and the three with my five

pick up both 2s and the 1 with my five

After profiling my code it shows that this is by far the most expensive part of the program (about 95 percent of execution time being spent here)

Can you see any way to optimize these methods?

this one actually generates all the possible moves.

private void generateMoves(Card myCard,ArrayList CurrentMove,
              ArrayList centerCards,ArrayList moves, int moveSum) {
    if(moveSum>myCard.value)
    {
        return;
    }
    else if(moveSum == myCard.value)
    {
        Move m = new Move(myCard, new ArrayList<>(CurrentMove));
        rateMove(m);
        moves.add(m);
        return;
    }

    for (Card card :centerCards) {
        if(!card.selected)
        {
            CurrentMove.add(card);
            card.selected = true;
            moveSum += card.value;
            generateMoves(myCard, CurrentMove, centerCards, moves, moveSum);
            moveSum -= card.value;
            CurrentMove.remove(card);
            card.selected = false;
        }
    }
}

this one removes any duplicates (the code above would return 4,1 and 1,4 as different moves from the example) I know its hacky but i couldn't think of anything that would be faster. Ideally they would be combined and duplicates would never be returned but i couldn't get it to work.

```
protected void removeDuplicates(ArrayList moves)
{
ArrayList temp = new ArrayList<>(moves);

for(Move move : temp)
{
while(moves.remo

In your recursive generateMoves method, you can reduce a huge amount of the duplicates by limiting where in the centerCards list you operate in.

My suggestion would be to pass that list through the recursion with a pointer to your current position in the array.... for example:

generateMoves(Card myCard,ArrayList CurrentMove,
          ArrayList centerCards, int centercardpos,
          ArrayList moves, int moveSum)

Then, in your method you can change the loop:

for (Card card :centerCards) { ...

to be:

for (int ci = centercardpos; ci < centerCards.size(); ci++) {
    Card card = centerCards.get(i);

        generateMoves(myCard, CurrentMove, centerCards,
               centercardpos + 1, // new increased limit.....
               moves, moveSum);

This will substantially reduce the number of possible moves (and still get the right answers). Reducing the values you gnerate will also substantially reduce duplicates, which in turn will also improve th pwerformance of removeDuplicates ...

The only time removeDuplicates will have effect is when you have something like (using your example: [5,4,3,2,1,2] ) the moves [5,2] and [5,2] (but the 'other' 2).

StackExchange Code Review Q#36055, answer score: 3