LeetCode Unique Binary Search Trees

 1 class Solution {
 2 public:
 3     int numTrees(int n) {
 4         return dfs(1, n);
 5     }
 6     
 7     int dfs(int start, int end) {
 8         if (start >= end) return 1;
 9         int count = 0;
10         // choose different number from [start, end] as the root
11         for (int i = start; i <= end; i++) {
12             // number of left tree cases * number of right tree cases
13             count += dfs(start, i - 1) * dfs(i + 1, end); 
14         }
15         return count;
16     }
17 };