[C++] Solution || Dynamic Programming Explained
Language Used: C++\n\nIf you have any questions, feel free to ask. If you like the solution and explanation, please upvote!\n\nTime: O(n^2);\nSpace: O(n)\n\n  d
**Language Used: C++**\n\n*If you have any questions, feel free to ask. If you like the solution and explanation, please **upvote!***\n\nTime: O(n^2);\nSpace: O(n)\n\n*  dp[i] := represents possible combinationswith ith element at its node;\n*  Lets arr[] be {x, y, x*y}; dp[0]:= contains possible ans for x as its root.\n*  Same goes for dp[1], but in dp[2] we need to check.\n*  Check whether x divides (x*y), if yes then it might acct as left node.\n*  Check whether right node is present (using hashmap).\n*  Save results in dp (dp[i] += dp[left] * dp[right]).\n\n```\nclass Solution {\npublic:\n    int numFactoredBinaryTrees(vector<int>& arr) {\n        constexpr int Mod = 1e9 + 7;\n        const int n = arr.size();\n        \n        sort(arr.begin(), arr.end());\n        \n        vector<long> dp(n, 1);\n        // Initialized with 1 because we can make atleast 1 BT with that number.\n        \n        unordered_map<int, int> Ind;\n        \n        for(int i{}; i<n; i++){\n            Ind[arr[i]] = i;\n        }\n        \n        for(int i{}; i<n; i++){\n            for(int j{}; j<i; j++){\n                if(arr[i]%arr[j] == 0){\n                    int rig = arr[i]/arr[j];\n\t\t\t\t\t// Checking whether right exists?\n                    if(Ind.count(rig)){\n                        dp[i] += dp[j] * dp[Ind[rig]];\n                        dp[i] %= Mod;\n                    }\n                }\n            }\n        }\n        \n        return accumulate(dp.begin(), dp.end(), 0L)%Mod;\n    }\n};\n```\nKeep Coding\n**`while(!success){ tryAgain(); } :)`**
['Dynamic Programming', 'C']