C++ || 2 Approaches || TC : O(N^2) SC : O(N) ✅
\n//Approach 1 : Top-Down Recursive Approach \n/*\n1 . First sort the array (Now we can say 2 number multiple is always its left side )\n2 . Using 2 Pointer fin
```\n//Approach 1 : Top-Down Recursive Approach \n/*\n1 . First sort the array (Now we can say 2 number multiple is always its left side )\n2 . Using 2 Pointer find out the 2 numbers (s=0 && e =n-1)\n3 . if arr[s]*arr[e]==arr[curInd] It means arr[s] and arr[e] is 2 child (and increase s++ and decrese e--)\n{\nIf we found 2 no then again recursively call for child (total no of tree formed using both child)\nchild1 = x\nchild2 = y\ntotal no of tree for current parent = x*y (if s==e)\nor\ntotal no of tree for current parent = 2 * x*y (if s!=e)\n}\n\tif arr[s]*arr[e]>arr[curInd] then we have to decrease our e--\n\telse s++\n4 .Using this approach we can find all no of pairs for every index \n*/\n/*\nExample : 2 10 4 5\n1 . sort the array :-> 2 4 5 10\n2 . start from index 0 or n-1( here i am starting with n-1) \ns = 0 \ne = 3-1 = 2\n2 4 5 10\n^   ^\nmul = 2*5 = 10\nHere we got 10 (2,5 is one pair)\n2!=5 (or s!=e)\ndp[curInd] = 2 * dp[s]*dp[e]\nagain call for n-1 recursively\n*/\nclass Solution {\npublic:\n    vector<int> dp;\n    int mod = 1000000007;\n    long solve(vector<int>&arr,int ind){\n        if(ind==-1) return 0; \n        if(dp[ind]!=-1) return dp[ind];\n        long cnt = 1;\n        int s = 0;\n        int e = ind-1;\n        while(s<=e){\n            long mul = (long)arr[s]*arr[e];\n            if(mul==arr[ind]){\n                long temp = (solve(arr,s) * solve(arr,e))%mod;\n                if(s!=e) temp=temp*2;\n                cnt = (cnt+temp)%mod;\n                s++;\n                e--;\n            }\n            else if(mul>arr[ind]) e--;\n            else s++;\n        }\n        return dp[ind] = cnt;\n    }\n    int numFactoredBinaryTrees(vector<int>& arr) {\n       sort(arr.begin(),arr.end());\n      dp.resize(arr.size(),-1);\n        long cnt = 0;\n        for(int i=0;i<arr.size();i++){\n            cnt=(cnt+solve(arr,i))%mod;\n        }\n        return cnt;\n    }\n};\n```\n\n```\n//Approach 2 : Bottom-Up \nclass Solution {\npublic:\n    int mod = 1000000007;\n    int numFactoredBinaryTrees(vector<int>& arr) {\n        sort(arr.begin(),arr.end());\n        vector<long> dp(arr.size(),1);\n        int ans = 0;\n        for(int i=0;i<arr.size();i++){\n            int s = 0;\n            int e = i-1;\n            while(s<=e){\n                long mul = (long)arr[s]*arr[e];\n                if(mul==arr[i]){\n                    long cnt = (dp[s]*dp[e]) %mod;\n                    if(s!=e) cnt*=2;\n                    dp[i]= (dp[i]+cnt)%mod;\n                    e--;\n                    s++;\n                }\n                else if(mul>arr[i]) e--;\n                else s++;\n            }\n            ans=(ans+dp[i])%mod;\n        }\n        return ans;\n    }\n};\n```\nIf You Like Please Upvote :)\nHappy Coding :)
['Dynamic Programming', 'C']