title: Problems in code to Print the possibilities of wins in a Coin game
body: <p><strong>I am solving the below problem using backtracking recursion. The first code "CoinGame1" is providing correct solution but the second code "CoinGame2" is providing a wrong solution. I guess, there is something bad happening since i am reversing the string earlier before calling recursively.</strong>  </p>
  
  <p>*Coin game: Alice and Bob are playing a game using a bunch of coins. The players pick several coins out of the bunch in turn. Each player can pick either 1 , 2 or 4 coins in each turn. Each time a player is allowed to pick coins,
  the player that gets the last coin is the winner. It is known that at last, when 1 , 2 or 4 coins are left, the player with first turn will definitely pick 1, 2 or 4 coins as required and win. For example, if there are 2 coins in end and Alice is the first player to pick, she will definitely pick 2 coins and win. Given the number of coins and the order of players (which means the first and the second players to pick the coins), write a program to print all the possibilities of winner
  of the game, </p>
  
  <pre>
  F(1, {alice,bob})
  alice
  F(6, {alice,bob})
  alice, bob, bob, alice, bob, bob
  F(4, {alice,bob})
  alice
  F(3, {alice,bob})
  bob, bob*
  
                           f(6,{A,B})                                     
                       /                \               \
              f(5,{B,A})                 f(4,{B,A})      f(2,{B,A})
            /     |      \                   B wins         B wins
  f(4,{A,B})  f(3,{A,B})  f(1,{A,B}) 
  A wins     /    |    \       A wins        
            /     |     \
  f(2,{B,A})  f(1,{B,A}) f(-1,{B,A})
  B wins         B wins       
  
  </pre>
  
  <p><strong>//SOLUTION1</strong></p>
  
  <pre><code>public class CoinGame1
  {
     public static void Count(int n, String[] s)   // n: no. of coins 
                                                 //s:{"Alice","Bob"} (order) 
    {
         if(n&gt;0)
         {
             if(n==1 || n==2 || n==4) System.out.println( s[0] );  // if 1/2/4 
                                   //coins left, the one with first chance wins
             else
             { 
                 Count(n-1,new String[]{s[1],s[0]});
                 Count(n-2,new String[]{s[1],s[0]});
                 Count(n-4,new String[]{s[1],s[0]});  
             }
         }
    }
  
    public static void main(String[] args)
        {
            String[] order = new String[]{"A","B"};
            Count(6,order);
        }
  }
  </code></pre>
  
  <blockquote>
    <p>java CoinGame1
    A
    B
    B
    A
    B
    B</p>
  </blockquote>
  
  <p><strong>//SOLUTION2</strong></p>
  
  <pre><code>public class CoinGame2
  {
     public static void Count(int n, String[] s)          // n: no. of coins    
                                                   //s:{"Alice","Bob"} (order) 
    {
         if(n&gt;0)
         {
             if(n==1 || n==2 || n==4) System.out.println( s[0] );  // if 1/2/4 
                                  //coins left, the one with first chance wins
             else
             {
                 String temp = s[0]; s[0] = s[1]; s[1] = temp;     // reverse s
                 Count(n-1,s);
                 Count(n-2,s);
                 Count(n-4,s);  
             }
         }
    }
  
    public static void main(String[] args)
        {
            String[] order = new String[]{"A","B"};
            Count(6,order);
        }
  }
  </code></pre>
  
  <blockquote>
    <p>java CoinGame2
    A
    B
    B
    B
    B
    B</p>
  </blockquote>