Problem Statement: This is a rather simple problem to describe. You will be given three numbers $S,P$ and $k$. Your task is to find if there are integers $n_1,n_2,\dots,n_k$ such that $n_1+n_2+\dots+n_k=S$, and $n_1 n_2\dots n_k=P$.
If such integers exist, print them out. If no such sequence of integers exist, then print "NO".
For example if $S=11,P=48$, and $k=3$ then $(3,4,4)$ is a solution. On the other hand, if $S=11,P=100$ and $k=3$, there is no solution and you should print "NO".
Given that, $1\leq k \leq 4$, $1 \leq S \leq 1000$ and $1\leq P \leq 1000$.
My Approach: $n_1,n_2,\dots,n_k$ have to satisfy two conditions: $n_1+n_2+\dots+n_k=S$, and $n_1 n_2\dots n_k=P$.
The second condition implies that $n_i$ 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 $k$-th 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.
I did get an "AC" (i.e. the solution passed all the test cases (using only the positive numbers, though nothing like "only positive integers" was mentioned)).
But I just wanted to know that can we do better, and find the solution more efficiently, because this approach will take up a lot of time with more number of variables. Is there any other way to solve this problem in that case?