With DP, Two-pointer, Combinotrics ( Maths ) and Sorting
\n Hey Guys, How are You all !!\n\n Lets start Today\'s problem solution.\n \n => Here, we have to find total valid binary tree which must follow below conditio
```\n Hey Guys, How are You all !!\n\n Lets start Today\'s problem solution.\n \n => Here, we have to find total valid binary tree which must follow below condition,\n         1) every parent is product of his child.\n\n => To solve this question some steps we will be following,\n       \n\t   1)  sort all array .\n\t          reason : because every element we are choosing as a root and we are finding two \n\t\t\t  element which product is this number another reason is we have to use two \n\t\t\t  pointer to find product so we need to sort.\n\t\t\t  \n\t\t2)  taverse fron first and make that node as a root node and find two element which\n\t\t    product is this root so that two number can be my child.\n\t\t\t\n\t\t\t=> now we need to use dp here because we are choosing child node but we need\n\t\t\t     to consider all subtree with this child node.\n\t\t\t\n\t\t\t      suppose, we have\n\t\t\t\t           50  as a root and 25 and 2 as a child,\n\t\t\t\t\t\t  25     2    \n\t\t\t\t\t\t5   5\n\t\t\t\t\t we are taking all combination of child like,\n\t\t\t\t    1)  50\n\t\t\t\t    2)   50 \n\t\t\t\t        25   2\n\t\t\t\t\t3)      50 \n\t\t\t\t\t     25   2\n\t\t\t\t\t  5    5\n\t\t\t\t\n\t\t\t 3) so  that\'s it we have all tree count in ith node so take sum of all dp and this is\n\t\t\t     our answer\n\t\t\t\n\t\t\t\n\t\t\n\t\nIf you not understood so take time and dry with pen and paper run because this problem uses concept of DP, Two-pointer, Combinotrics ( Maths ) and Sorting.\n  \n```\n\n **Code**\n\n```\nclass Solution {\npublic:\n    int mod=1e9 + 7;\n    int numFactoredBinaryTrees(vector<int>& nums) {\n        int n=nums.size();\n        sort(nums.begin(),nums.end());\n        vector<int>dp(n,1);\n        \n        for(int i=1;i<n;i++)\n        {\n            int f=0,e=i-1;\n           unsigned long long tar=nums[i];\n            \n            while(f<=e)\n            { \n               unsigned long long pro=1LL*nums[f]*nums[e];\n                \n                if(pro==tar){\n                    \n                    dp[i]=(dp[i] + (1LL*dp[f]*dp[e]))%mod;\n                \n                    if(f!=e){\n                        dp[i]=(dp[i] + (1LL*dp[f]*dp[e]))%mod;\n                    }\n                    \n                    f++;\n                    e--;\n                }else if(pro<tar)\n                {\n                    f++;\n                }else{\n                    e--;\n                }\n            }\n            \n        }\n        \n        int ans=0;\n       \n        for(int i=0;i<n;i++){\n            ans= (ans + dp[i])%mod;\n        }\n        \n        return ans;\n    }\n};\n```\n
['Dynamic Programming', 'Binary Tree']