If I were to find a set of 10 positive integers whose sum = 87248 and the sum of their squares = 447804117.
Using an efficient dynamic programming, what will be time complexity of this kind of problem?
(Additional constraints are: each integer is less than or equal to 65536, repetition is allowed and order is not important. A lexicographic order is followed in representing a set)
[The desired output set is (2, 6, 32, 65, 546, 546, 3248, 4322, 12981, 65500)]
I just got started with dynamic programming, excuse me for any assumptions
Such problems can be solved (although not your original one, since if a sum of integers is even, the sum of their squares must also be even). Dynamic programming can be used, although if you want to solve $$ \sum_{i=1}^n x_i = A, \qquad \sum_{i=1}^n x_i^2 = B, $$ the obvious way of doing it via dynamic programming takes time around $O(n A^2 B)$, which is probably not efficient enough for your original problem.
However, you can still solve it. Every integer is the sum of four squares, which means that every integer is the sum of ten squares in many, many, many different ways. So what you can do is pick two of the numbers cleverly to get a solvable problem with much smaller parameters. For example, if you pick two of the numbers to be 23155 and 62866, you are left with finding eight integers whose sum is 1227 and whose sum of squares is 299089. How did I do this? I solved a quadratic equation whose parameters I chose so that it would reduce the size of the problem as much as possible with the constraint that the remaining problem would probably still have many solutions. The only reason this trick works is because the original equation has an incredibly large number of solutions.
I now had a problem that was clearly solvable by computer using dynamic programming, but it was still a little bit large (I'm lazy, so I prefer to write my programs in a math software package rather than C), so I figured why not use the same trick again. This time I got an almost trivial dynamic program. Choosing 168 and 459 as two more of the numbers, we get the problem of finding six positive integers whose sum is 600 and whose sum of squares is 60184. Now, we can subtract 100 from each of these positive integers to yield the problem of finding six integers whose sum is 0 and whose sum of squares is 184.
My dynamic program says that there are 32760 solutions to this final problem, counting permutations and negations of solutions as different solutions. This means that there are at least 24 essentially distinct solutions.
The results:
\begin{eqnarray*} 94^2+95^2+99^2+100^2+101^2+111^2+168^2+459^2+23155^2+62866^2 &=& 4488587070\cr 2^2+6^2+32^2+65^2+546^2+546^2+3248^2+4322^2+12981^2+65500^2 &=& 4488587070 \end{eqnarray*}
How does the dynamic program work?
What you do is make an $n \times A \times B$ array, where the $(m,a,b)$ element is $1$ if there are $m$ integers whose sum is $a$ and whose sum of squares is $b$ and $0$ otherwise. Fill it in using the standard dynamic programming techniques.
You could presumably automate the process of finding the quadratic equation to reduce the parameters as much as possible, although it would have taken me more thought than doing it by hand. I didn't figure out the best way to write down this equation for a general triple $n, A, B$. (There was some trial and error involved; the first time I tried it I got a problem with smaller parameters that had no solutions because I didn't maintain the proper relation between the sum and the sum of squares.)