package leetcode;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * https://leetcode.com/problems/unique-binary-search-trees/
 */
public class Problem96 {
    public int numTrees(int n) {
        List<Integer> list = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            list.add(i);
        }
        List<List<Integer>> p = permutation(list);
        return (n % 2 == 0) ? p.size() : p.size()-1;
        
//        Set<String> set = new HashSet<>();
//        for (List<Integer> l : p) {
//            StringBuilder sb = new StringBuilder();
//            TreeNode root = null;
//            System.out.println(l);
//            for (int i : l) {
//                root = buildBst(root, i, "C", 1, sb);
//            }
//            System.out.println(sb.toString());
//            set.add(sb.toString());
//        }
//        return set.size();
    }
    
//    private static class TreeNode {
//        int val;
//        TreeNode left;
//        TreeNode right;
//        
//        public TreeNode(int val) {
//            this.val = val;
//        }
//    }
//    
//    private TreeNode buildBst(TreeNode node, int val, String s,
//        int level, StringBuilder sb) {
//        if (node == null) {
//            sb.append(s + level);
//            return new TreeNode(val);
//        }
//        if (node.val >= val) {
//            node.left = buildBst(node.left, val, "L", level+1, sb);
//        } else {
//            node.right = buildBst(node.right, val, "R", level+1, sb);
//        }
//        return node;
//    }
    
    private List<List<Integer>> permutation(List<Integer> list) {
        List<List<Integer>> result = new ArrayList<>();
        permutation(list, new ArrayList<>(), result);
        return result;
    }
    
    private void permutation(List<Integer> input, List<Integer> accu,
        List<List<Integer>> result) {
        if (input.isEmpty()) {
            result.add(accu);
            return;
        }
        for (int i = 0; i < input.size(); i++) {
            List<Integer> newAccu = new ArrayList<>();
            for (int a : accu) {
                newAccu.add(a);
            }
            List<Integer> remainder = new ArrayList<>();
            for (int j = 0; j < input.size(); j++) {
                if (i == j) {
                    newAccu.add(input.get(i));
                } else {
                    remainder.add(input.get(j));
                }
            }
            permutation(remainder, newAccu, result);
        }
    }
    
    public static void main(String[] args) {
        Problem96 prob = new Problem96();
        System.out.println(prob.numTrees(10));
    }
}

@@ -16,36 +16,8 @@
 e;%0A%0A
-import java.util.ArrayList;%0A
 impo
@@ -33,19 +33,19 @@
 til.Hash
-Set
+Map
 ;%0Aimport
@@ -59,34 +59,11 @@
 til.
-List;%0Aimport java.util.Set
+Map
 ;%0A%0A/
@@ -163,1117 +163,103 @@
     
-public int numTrees(int n) %7B%0A        List%3CInteger%3E list = new ArrayList%3C%3E();%0A        for (int i = 1; i %3C= n; i++) %7B%0A            list.add(i);%0A        %7D%0A        List%3CList%3CInteger%3E%3E p = permutation(list);%0A        return (n %25 2 == 0) ? p.size() : p.size()-1;%0A        %0A//        Set%3CString%3E set = new HashSet%3C%3E();%0A//        for (List%3CInteger%3E l : p) %7B%0A//            StringBuilder sb = new StringBuilder();%0A//            TreeNode root = null;%0A//            System.out.println(l);%0A//            for (int i : l) %7B%0A//                root = buildBst(root, i, %22C%22, 1, sb);%0A//            %7D%0A//            System.out.println(sb.toString());%0A//            set.add(sb.toString());%0A//        %7D%0A//        return set.size();%0A    %7D%0A    %0A//    private static class TreeNode %7B%0A//        int val;%0A//        TreeNode left;%0A//        TreeNode right;%0A//        %0A//        public TreeNode(int val) %7B%0A//            this.val = val;%0A//        %7D%0A//    %7D%0A//    %0A//    private TreeNode buildBst(TreeNode node, int val, String s,%0A//        int level, StringBuilder sb) %7B%0A//        if (node == null) %7B%0A//            sb.append(s + level);%0A//    
+/*%0A     * http://en.wikipedia.org/wiki/Catalan_number%0A     */%0A    public int numTrees(int n) %7B%0A
     
@@ -274,658 +274,131 @@
 rn n
-ew 
+um
 Tree
-Node(val);%0A//        %7D%0A//        if (node.val %3E= val) %7B%0A//            node.left = buildBst(node.left, val, %22L%22, level+1, sb);%0A//        %7D else %7B%0A//            node.right = buildBst(node.right, val, %22R%22, level+1, sb);%0A//        %7D%0A//        return node;%0A//    %7D%0A    %0A    private List%3CList%3CInteger%3E%3E permutation(List%3CInteger%3E list) %7B%0A        List%3CList%3CInteger%3E%3E result = new ArrayList%3C%3E();%0A        permutation(list, new ArrayList%3C%3E(), result);%0A        return result;%0A    %7D%0A    %0A    private void permutation(List%3CInteger%3E input, List%3CInteger%3E accu,%0A        List%3CList%3CInteger%3E%3E result) %7B%0A        if (input.isEmpty()) %7B%0A            result.add(accu);
+s(n, new HashMap%3C%3E());%0A    %7D%0A    %0A    private int numTrees(int n, Map%3CInteger, Integer%3E memo) %7B%0A        if (n == 0) %7B
 %0A   
@@ -412,16 +412,18 @@
   return
+ 1
 ;%0A      
@@ -438,238 +438,96 @@
     
-for (int i = 0; i %3C input.size(); i++) %7B%0A            List%3CInteger%3E newAccu = new ArrayList%3C%3E();%0A            for (int a : accu) %7B%0A                newAccu.add(a);%0A            %7D%0A            List%3CInteger%3E remainder = new ArrayList%3C%3E()
+if (memo.containsKey(n)) %7B%0A            return memo.get(n);%0A        %7D%0A        int sum = 0
 ;%0A  
@@ -532,20 +532,16 @@
         
-    
 for (int
@@ -545,34 +545,24 @@
 int 
-j = 0; j %3C input.size(); j
+i = 1; i %3C= n; i
 ++) 
@@ -579,229 +579,59 @@
     
-    if (i == j) %7B%0A                    newAccu.add(input.get(i));%0A                %7D else %7B%0A                    remainder.add(input.get(j));%0A                %7D%0A            %7D%0A            permutation(remainder, newAccu, result
+sum += numTrees(i - 1, memo) * numTrees(n - i, memo
 );%0A 
@@ -647,147 +647,48 @@
     
-%7D%0A
     
-%0A    public static void main(String%5B%5D args) %7B%0A        Problem96 prob = new Problem96();%0A        System.out.println(prob.numTrees(10))
+memo.put(n, sum);%0A        return sum
 ;%0A  

Solve problem 96 (thanks Wikipedia)