Problem Link: CodeChef: Practical coding for everyone
My Approach: n1, n2, …, nk have to satisfy two conditions: n1+n2+…+nk = S and n1.n2…nk = P. The second condition implies that ni is a divisor of P for all valid i hence we can narrow down the search using this fact**. So I factored the number P and stored its divisors. Next I implemented a recursive solution to fill each variable and solve the sub problem with one less variable to fill each time. I did this only for (k-1) variables as the kth variable is fixed automatically by the first condition.
**I came to this conclusion because I found that any number less than or equal to 1000 has at most 32 divisors (for reference https://www.geeksforgeeks.org/querying-maximum-number-divisors-number-given-range/), which means a total of 64 (taking both the negative as well as positive divisors as the problem only says integers and not positive integers) resulting in a total of 64^4 = 16777216 possibilities which can easily be searched through in time.
Link to Submission: CodeChef: Practical coding for everyone
But now the problem is that this code gives a WA on one test case and I can’t figure out why. Can anybody please help?
[If you have had a look at the code can you also tell me what happens if I pass something like solve(varUsed++,…) instead of solve(varUsed+1,…). I know it results into an error, but why?]