import java.util.*;

class Recursion  {
    /**
       Given a set represented as a list, return its power set.
    **/
    public static <E> ArrayList<ArrayList<E>> powerSet(ArrayList<E> s){
        ArrayList<ArrayList<E>> ps = new ArrayList<ArrayList<E>>();
        if (s.size()==0){
            ps.add(new ArrayList<E>());
            return ps;
        }
        E x = s.remove(s.size()-1);
        ArrayList<ArrayList<E>> ps1 = powerSet(s);
        ps.addAll(ps1);
        for (ArrayList<E> r : ps1){
            r = copy(r);
            r.add(x);
            ps.add(r);
        }
        return ps;
    }

    public static <E> ArrayList<E> copy(ArrayList<E> s){
        ArrayList<E> cs = new ArrayList<E>();
        for (E e : s){
            cs.add(e);
        }
        return cs;
    }

    /**
       Given a set s, return a set of n-element subsets of s. Assume n <= size(s).
    **/
    public static <E> ArrayList<ArrayList<E>> subSets(ArrayList<E> s, int n){
        ArrayList<E> s1 = copy(s);
        ArrayList<ArrayList<E>> subsets = new ArrayList<ArrayList<E>>();
        if (n == 0){
            subsets.add(new ArrayList<E>());
            return subsets;
        }
        if (s1.size()==n){
            subsets.add(s1);
            return subsets;
        }
        E x = s1.remove(s1.size()-1);
        subsets.addAll(subSets(s1,n));
        for (ArrayList<E> r : subSets(s1,n-1)){
            r = copy(r);
            r.add(x);
            subsets.add(r);
        }
        return subsets;
    }

    /**
       Given a list, return a list of all of the permutations of the list.
    **/
    public static <E> ArrayList<ArrayList<E>> permutations(ArrayList<E> lst){
        ArrayList<ArrayList<E>> perms = new ArrayList<ArrayList<E>>();
        int n = lst.size();
        if (n==0){
            perms.add(new ArrayList<E>());
            return perms;
        }
        for (int i = 0; i < n; i++){
            ArrayList<E> lst1 = copy(lst);
            E x = lst1.get(i);
            lst1.remove(i);
            ArrayList<ArrayList<E>> perms1 = permutations(lst1);
            for (ArrayList<E> p : perms1){
                p.add(x);
                perms.add(p);
            }
        }
        return perms;
    }
    
    /**
       Binomial coefficient: C(n,k) n choose k.
    **/
    static int bc(int n, int k, Integer[][] memo){
        Integer res = memo[n][k];
        if (res != 0)
            return res;
        if (k==0) return 1;
        if (n==k) return 1;
        res = bc(n-1,k,memo)+bc(n-1,k-1,memo);
        memo[n][k] = res;
        return res;
    }

    /**
       The backtracking algorithm for the N-queens problem.
    **/
    static void nqueens(int n){
        Integer[] queenArray = new Integer[n];
        placeQueens(queenArray,0);
    }
    
    static boolean placeQueens(Integer[] queenArray, int col){
        int n = queenArray.length;

        if (col == n){
            for (Integer e: queenArray)
                System.out.print(e+" ");
            System.out.println();
            return true;
        }
        int row = 0;
        while (row < n){
            if (!attack(queenArray,col,row)){
                queenArray[col] = row;
                if (placeQueens(queenArray, col+1))
                    return true;
            } 
            row++;
        }
        return false;
    }
    
    static boolean attack(Integer[] queenArray, int col, int row){
        for (int col1 = 0; col1 < col; col1++)
            if (row == queenArray[col1] ||
                row+col == queenArray[col1]+col1 ||
                row-col == queenArray[col1]-col1)
                return true;
        return false;
    }

    public static void main(String[] args){
        ArrayList<Integer> s = new ArrayList<Integer>();
        s.add(1);
        s.add(2);
        s.add(3);
        System.out.println("\npowerSet of {1,2,3}");
        System.out.println(powerSet(s));

        System.out.println("\npermutations of {1,2,3}");
        ArrayList<Integer> lst = new ArrayList<Integer>();
        lst.add(1);
        lst.add(2);
        lst.add(3);
        lst.add(4);
        System.out.println(permutations(lst));        

        ArrayList<Integer> s1 = new ArrayList<Integer>();
        s1.add(1);
        s1.add(2);
        s1.add(3);
        s1.add(4);
        System.out.println("\n2-element subsets of {1,2,3}");
        System.out.println(subSets(s1,2));

        Integer[][] memo = new Integer[26][6];
        for (int i = 0; i<26; i++)
            for (int j = 0; j<6; j++)
                memo[i][j] = 0;
        System.out.println("\nbc(25,5)=" + bc(25,5,memo));
        nqueens(8);
    }
}