https://leetcode.com/problems/binary-trees-with-factors

Let dp(num) be the answer to the question: how many binary trees exists such that their root equal to num and they follow the problem statement. We can calculate this number of trees, if we look at the left subtree and at the right subtree. So, first of all we create s_arr: set of possible values, and then for each cand in s_arr, we check:

  1. If num % cand == 0, that is number is divisible.
  2. If num//cand in s_arr, that is if the second children also in set of admissible values.
  3. We add dp(cand)*dp(num//cand) to ans, total number of trees we found. Note that we define ans = 1, because we can always have tree with one node.

Complexity: time complexity is O(n^2), because we have n different states and from each state we make at most O(n) steps. Space complexity is O(n).

class Solution:
    def numFactoredBinaryTrees(self, arr):
        s_arr, N = set(arr), 10**9 + 7
        
        @lru_cache(None)
        def dp(num):
            ans = 1
            for cand in s_arr:
                if num % cand == 0 and num//cand in s_arr:
                    ans += dp(cand)*dp(num//cand)
            return ans
        
        return sum(dp(num) for num in s_arr) % N

If you like the solution, you can upvote it on leetcode discussion section: Problem 0823