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 forloops iteratingi
andj
. 
Space Complexity: , the space used by
dp
andindex
.
Analysis written by: @awice.