#### Approach #1: Dynamic Programming [Accepted]

Intuition

The largest value v used must be the root node in the tree. Say dp(v) is the number of ways to make a tree with root node v.

If the root node of the tree (with value v) has children with values x and y (and x * y == v), then there are dp(x) * dp(y) ways to make this tree.

In total, there are ways to make a tree with root node v.

Algorithm

Actually, let dp[i] be the number of ways to have a root node with value A[i].

Since in the above example we always have x < v and y < v, we can calculate the values of dp[i] in increasing order using dynamic programming.

For some root value A[i], let's try to find candidates for the children with values A[j] and A[i] / A[j] (so that evidently A[j] * (A[i] / A[j]) = A[i]). To do this quickly, we will need index which looks up this value: if A[k] = A[i] / A[j], then index[A[i] / A[j]] = k.

After, we'll add all possible dp[j] * dp[k] (with j < i, k < i) to our answer dp[i]. In our Java implementation, we carefully used long so avoid overflow issues.

class Solution {
public int numFactoredBinaryTrees(int[] A) {
int MOD = 1_000_000_007;
int N = A.length;
Arrays.sort(A);
long[] dp = new long[N];
Arrays.fill(dp, 1);

Map<Integer, Integer> index = new HashMap();
for (int i = 0; i < N; ++i)
index.put(A[i], i);

for (int i = 0; i < N; ++i)
for (int j = 0; j < i; ++j) {
if (A[i] % A[j] == 0) { // A[j] is left child
int right = A[i] / A[j];
if (index.containsKey(right)) {
dp[i] = (dp[i] + dp[j] * dp[index.get(right)]) % MOD;
}
}
}

long ans = 0;
for (long x: dp) ans += x;
return (int) (ans % MOD);
}
}

class Solution(object):
def numFactoredBinaryTrees(self, A):
MOD = 10 ** 9 + 7
N = len(A)
A.sort()
dp = [1] * N
index = {x: i for i, x in enumerate(A)}
for i, x in enumerate(A):
for j in xrange(i):
if x % A[j] == 0: #A[j] will be left child
right = x / A[j]
if right in index:
dp[i] += dp[j] * dp[index[right]]
dp[i] %= MOD

return sum(dp) % MOD


Complexity Analysis

• Time Complexity: , where is the length of A. This comes from the two for-loops iterating i and j.

• Space Complexity: , the space used by dp and index`.

Analysis written by: @awice.