Express any number as a sum of as few squares as possible

Question

All in the title. Ex: 16=4**2 15=1**2+1**2+3**2+2**2
191=9*9+3*3+10*10+1*1

Very interesting answer from Louis so he wins even if his code is not solving 100% of the problem.

Answer 1

Try this
https://code.sololearn.com/c6DuuGjp8imR/?ref=app

Answer 2

Got it
also
191 = 13²+3²+3²+2²

https://code.sololearn.com/cLBdlCIrckam/?ref=app

Answer 3

Interesting
https://code.sololearn.com/cd3z4AGXtI3B/?ref=app

Answer 4

@VcC Thanks, yes I agree, it may not catch all combinations of 4. I will think about it, maybe use all items in 2dictionary and add them together 1 by one to create a 4dictionary.
So show us your mindboggling oneliner.

Answer 5

Here you are my friend. Complexity could be reduced by testing if n is a square or if n is in q but would make the oneliner longer ;-) https://code.sololearn.com/cYArjkqNaSzO/?ref=app

Answer 6

@Louis Your code is fast and gives one decomposition but not the smaller one. ex for 191 you give 5 numbers but there are shorter options...

Answer 7

Here is another way of doing It with combinations, but I don't know if It will be quick enough for big numbers here in sololearn, but I tried It on the pc and It works perfectly, still thinking how to fix my other code btw xD
https://code.sololearn.com/cpXR0OVS4X4C/?ref=app

Answer 8

very interesting code. very good idea to use sets. the only limitation is that you are not sure to end up with a sum of 4.

Answer 9

@louis i m finishing it because your idea made improve it

Answer 10

It's a little too late, but I did something that seems to work, finding maximum 4 factors for each number, see if you like It xD
https://code.sololearn.com/coTo6XHEMyzE/?ref=app

Answer 11

not working for 704

Answer 12

Yep was a mistake. It was 10 not 2. You only need 4 squares

Answer 13

Now go and code !

Answer 14

Not working for 704=8**2+8**2+24**2
or for 384=8,8,16

Answer 15

Yeah, there are some that can be done with less than 4 numbers and my Code does It with 4, thats the problem right?

Answer 16

@lucas you only need to consider x>=y>=z>=t tuples. look at louis' or my code for additionnal imprvements