Algorithms: How to find k numbers with given sum and product.

[meteora]

If we are given a number k (1 <= k <= 4) and two numbers S (1 <= S <= 1000 ) and P (1 <= P <= 1000), we have to find a sequence of k numbers such that, the sum of all elements in the sequence is S and their product is P. Print NO if the sequence does not exist and print the sequence otherwise.

We can brute-force all the cases as k is very small,

 if k == 1
     then do ...
if k == 2
     then do ...
if k == 3
     then do ...
if k == 4
     then do ...

For cases 1 and 2 it is very easy to find the sequence.
But i have no idea how we find it for k = 3 and k = 4.
Please help me to solve this problem.

[helios]

Hint: Start from the divisors of P.

[meteora]

If k = 3,

we find the factors of P x*y till x = sqrt of p.

For each pair x*y (x < y)
we try to solve the problem for k = 2, S = S-x and P = y.

And for k = 4, we do the same thing as before using recursion.
Is this a correct way to solve?

[helios]

Pretty much, although I'm not sure I'd be so eager to discard the range (sqrt(P);P]. I'm not saying it's wrong, just that I'm not entirely sure it's correct.

[meteora]

Nor am i. But i will try to code it up and see, its actually this problem: http://opc.iarcs.org.in/index.php/problems/FINDNUMS
And thanks for your hint :D

[helios]

Oh, and don't forget the negative divisors, just in case.

[meteora]

Yes, you are right i forgot.

[meteora]

I submitted my code and got Accepted, thanks for your help.

[JLBorges]

Recursive:

Let F( M, K, S, P ) be a set of K integers >= M, with sum == S and product == P

Specific problem: Find F( 1, K, S, P )

General problem: find F( M, K, S, P ):

1. if M > (S-K+1) or M > P there is no solution

2. let the smallest number >= M that divides P be x

3. find F( x+1, K-1, S-x, P/x ) 

4a. if found, [x] union F( x+1, K-1, S-x, P/x ) is the solution

4b. else find F( x+1, K, S, P )