LeetCode: Binary Trees With Factors Solution

Approach

Multiplying as result of combination

Implementation

1/**
2 * @param {number[]} arr
3 * @return {number}
4 */
5var numFactoredBinaryTrees = function (arr) {
6  const set = new Set(arr)
7  const memo = new Map()
8  const recursion = el => {
9    if (memo.has(el)) {
10      return memo.get(el)
11    }
12    let count = 1
13    for (const otherEl of arr) {
14      if (el % otherEl === 0 && set.has(el / otherEl)) {
15        count += recursion(otherEl) * recursion(el / otherEl)
16      }
17    }
18    memo.set(el, count)
19    return count
20  }
21
22  return arr.reduce((acc, el) => (acc += recursion(el)), 0) % (1e9 + 7)
23}