[Python] Short O(n^2) solution, explained
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 calculat
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:\n\n1. If `num % cand == 0`, that is number is divisible.\n2. If `num//cand in s_arr`, that is if the second children also in set of admissible values.\n3. 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.\n\n**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)`.\n\n```\nclass Solution:\n    def numFactoredBinaryTrees(self, arr):\n        s_arr, N = set(arr), 10**9 + 7\n        \n        @lru_cache(None)\n        def dp(num):\n            ans = 1\n            for cand in s_arr:\n                if num % cand == 0 and num//cand in s_arr:\n                    ans += dp(cand)*dp(num//cand)\n            return ans\n        \n        return sum(dp(num) for num in s_arr) % N\n```\n\nIf you have any question, feel free to ask. If you like the explanations, please **Upvote!**
['Dynamic Programming']