We need to find the least number of perfect squares that sum up to a given number. With problems like this, the brute-force method seems to lean towards iterating through all the possible numbers and performing some operation at each step.
It seems from the get-go that we'll need to find all the perfect squares available to us before we reach the specified number in an iteration.
This means if the number is 30
, we'll start at 1
, then 2
, and conduct a logical step at each number. But what logic do we need? Well, if we're given a number-- say, 100
, how would we manually solve this problem and find the perfect squares that sum up to 100
?
Like we said, we'd probably just start with 1
and get its perfect square. Then we'll move on to 2
, and get the perfect square of 4
. But in this case, we'll keep summing as we calculate each square. Mathematically speaking, it would look like:
xxxxxxxxxx
// while (1*1) + (2*2) + (3*3) + (4*4) + ... <= 100