CareerCup

Sort the array, remove duplicates, then count recursively picking every i-th element as the root, with 0..i-1 being left subtree, i+1..N right subtree. See solution to leetcode 96.

Remove duplicates from the array now array has unique integers.
int countTrees(int n){
int T[] = new int[n+1];
T[0] = 1;
T[1] = 1;
for(int i=2; i <= n; i++){
for(int j=0; j <i; j++){
T[i] += T[j]*T[i-j-1];
}
}
return T[n];
}

This is about "Catalan Number". As 'adr' said, i took a look leetcode#96 but i also found there couple of excellent youtube out there. easy to understand..

#include <unordered_set>
#include <vector>
#include <iostream>

using namespace std;

class Node
{
    public:
        Node(int min_idx, int max_idx)
        {
            min_idx_ = min_idx;
            max_idx_ = max_idx;
        }
        int min_idx_, max_idx_;
};

void Count(const vector<int>& a, unordered_set<int>& seen, vector<Node> &nodes, int nodes_start, int& count)
{
    if (seen.size() == a.size())
    {
        if (!a.empty())
        {
            ++count;
        }
        return;
    }
    for (int j = nodes_start; j < nodes.size(); ++j)
    {
        const Node n = nodes[j];
        for (int i = n.min_idx_; i <= n.max_idx_; ++i) {
            if (seen.find(i) == seen.end()) {
                seen.insert(i);
                nodes.push_back(Node(n.min_idx_, i - 1));
                nodes.push_back(Node(i + 1, n.max_idx_));
                Count(a, seen, nodes, j + 1, count);
                nodes.pop_back();
                nodes.pop_back();
                seen.erase(i);
            }
        }
    }
}

int main()
{
    vector<int> a = {7, 9, 1};
    sort(a.begin(), a.end());
    unordered_set<int> seen;
    vector<Node> nodes = {Node(0, a.size() - 1)};
    int count = 0;
    Count(a, seen, nodes, 0, count);
    cout << count << "\n";
    return 0;
}