using backtracking we get the solution, but if we check for all the possible combinations ,it gives tle like for n=5 it will have 59049 numbers. Here is my code-
https://www.codechef.com/viewsolution/31922026
but from all possible numbers if we remove numbers like for n=5,
1 1 1 2 1
1 1 1 3 1
1 1 1 3 2
.
.
total numbers will be 1287 ,much lesser that 59049
it gets AC.
here is my AC solution
https://www.codechef.com/viewsolution/31922657
my question is what is the reason for removing such numbers ?
is this true decreasing number sequence or first increasing then decreasing whose sum of squares is not a squared number
like
11121=(1*1)+(1*1)+(1*1)+(2*2)+(1*1)=8
There is no number whose square is 8
3211=(3*3)+(2*2)+(1*1)+(1*1)=15
There is no number whose square is 15