Technical interviews: Recursive

Question1:
Implement an algorithm to place 8 queens on an 8 x 8 chessboard so that no two queens attack each other.
See the solution 
 
package com.hong.recursive;

/**
 * @author HongQing
 *
 */
public class EightQueens {
    
    public static int count = 0;
    
    public static boolean validateMove(int[][] chessBoard, int row, int col){   
            
            for(int i = 0; i < row; i++)
            {
                for(int j = 0; j < chessBoard[0].length; j++)
                {
                    if(chessBoard[i][j] == 1)
                    {
                        if(j == col) //Attacks each other on the same column.
                            return false;
                        else
                        {
                            if( (row - i) == Math.abs(col-j)) //Attacks each other on the same diagonal. 
                            {
                                return false;
                            }
                        }
                    }
                }
                
            }
            return true;
    }
    
    
    public static void eightQueen(int[][] chessBoard)
    {   
        for(int i = 0; i < chessBoard.length; i++)
        {
            chessBoard[0][i] = 1;
            
            //Call placeQueen method to find a valid position for the next queen on the next row.
            placeQueen(chessBoard,1, i ); 
            
            chessBoard[0][i] = 0; 
        }
    }
    
    public static void placeQueen(int[][] chessBoard, int row, int col)
    {
            if(row == 8) //The last queen has been placed at the right place.
            {
                print(chessBoard);
                return;
            }
            
            //Check for the next valid place on next row.
            for(int i = 0; i < chessBoard.length; i++)
            {
                if(validateMove(chessBoard, row, i)) 
                {
                    //Place the queen and move on the next row.
                    chessBoard[row][i] = 1; 
                    placeQueen(chessBoard, row+1, i);
                    
                    //Erase the previous move and search for the next possibility on the same row.
                    chessBoard[row][i] = 0;  
                }
                
            }
    }
    
    //Test case.
    public static void main(String[] args)
    {
        int[][] chessBoard = {  {0,0,0,0,0,0,0,0},
                                {0,0,0,0,0,0,0,0},
                                {0,0,0,0,0,0,0,0},
                                {0,0,0,0,0,0,0,0},
                                {0,0,0,0,0,0,0,0},
                                {0,0,0,0,0,0,0,0},
                                {0,0,0,0,0,0,0,0},
                                {0,0,0,0,0,0,0,0} };
                eightQueen(chessBoard);
    }
    
    //Print out a solution.
    public static void print(int[][] chessBoard)
    {
            System.out.println("Queen: " + (++count));
            System.out.println("-------------------------");
            
            for(int i = 0; i < chessBoard.length; i++)
            {  
                System.out.print("|");
                for(int j = 0; j < chessBoard[0].length; j++)
                {
                    if(chessBoard[i][j] == 1)
                        System.out.print("Q |");
                    else
                        System.out.print("  |");
                }
                System.out.println();
                System.out.println("-------------------------");
            }
    }
    
}
Question2:
Implement an algorithm to generate all subsets of a set. 
Example: 
A set is {3, 2, 1} then its subsets are {}, {1}, {2}, {3}, {1,2}, 
{1,3}  {2, 3}, and {1, 2, 3}.
See the solution 
 
package com.hong.recursive;

import java.util.ArrayList;
import java.util.List;

/**
 * @author HongQing
 *
 */

public class Subsets {
    
    public static List<List<Integer>> subSets(ArrayList<Integer> target, int index)
    {
            List<List<Integer>> resultSets = new ArrayList<List<Integer>>();
            
            if(index == target.size())
                return resultSets;
        
            int firstElement = target.get(index);   
            resultSets = subSets(target, index +1 );
        
            List<List<Integer>> tempContainer = new ArrayList<List<Integer>>();
            for(List<Integer> set : resultSets)
            {  
                List<Integer> newSet = new ArrayList<Integer>(); 
                newSet.add(firstElement);
                newSet.addAll(set);
                tempContainer.add(newSet);
            }
            
            resultSets.addAll(tempContainer);;
            List<Integer> newSet = new ArrayList<Integer>();
            newSet.add(firstElement);
            
            resultSets.add(newSet);
            
            return resultSets;
        
    }
    
    public static void main(String[] args)
    {
        ArrayList<Integer> set = new  ArrayList<Integer>();
        
        set.add(3);
        set.add(2);
        set.add(1);
    
        List<List<Integer>> subSets = subSets(set,0);
        
        for(List<Integer> subSet : subSets)
        {
            for(Integer i : subSet)
            {
                System.out.print(i + " ");
            }
            System.out.println();
        }
        
    }

}
Question3:
Given some dollar value in cents (e.g. 200 = 2 dollars, 1000 = 10 dollars), write a program to calculate the number of ways of representing the dollar value by combintation of coins. There are only penny, nickel, dime, and quarter. (quarter = 25 cents, dime = 10 cents, nickel = 5 cents, penny = 1 cent)
See the solution 
package com.hong.recursive;

/**
 * @author HongQing
 *
 */

public class CoinCombination {
    
    private static final int QUARTER = 25;
    private static final int DIME = 10; 
    private static final int NICKEL = 5; 
    private static final int PENNY = 1;
    
    /*
     * Recursive solution.
     * The problem can be solved iteratively as well.(Will be implemented later)
     */
    public static int coinCombination(int value, int coinValue)
    {
        int nextCoin = 0; 
        
        switch(coinValue)
        {
        case QUARTER:
            nextCoin = DIME;
            break; 
        case DIME:
            nextCoin = NICKEL; 
            break; 
        case NICKEL:    
            nextCoin = PENNY;
            break;
        case PENNY:  //Base case, return 1.
            return 1;
        }
        
        int totalWays = 0; 
        
        for(int i = 0; i * coinValue <= value; i++)
        {   
            totalWays += coinCombination(value - i*coinValue, nextCoin );
        }
        
        return totalWays;
        
    }
    
    public static void main(String[] args)
    {
        //Value is 3 cents, then output is 1.
        System.out.println(coinCombination(3, 25));
        
        //Value is 5 cents, then output is 2. 
        System.out.println(coinCombination(5, 25));
        
        //Value is 10 cents,then output is 4. 
        System.out.println(coinCombination(10, 25));
        
        //Value is 25 cents, then output is 13.
        System.out.println(coinCombination(25,25));
        
    }

}