## Problem

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, …) which sum to n.

Example 1:

```
Input: n = 12
Output: 3
Explanation: 12 = 4 + 4 + 4.
```

Example 2:

```
Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.
```

## Thought Process

- since 1 is a perfect square, so for any n, there must be a solution, the worst case is n
- I tried the brute force solution but failed, i.e. find the biggest perfect score the number can hold e.g. 9 for 12:
- e.g. 12 = 9 + 3, and 3 can only be 1 + 1 + 1, giving an result of 4
- however, 12 = 4 + 4 + 4, which is 3

- One solution is to model the problem as an unweighted graph:
- for numbers from 0 to n, each number is a point
- connect two points x, y if the distance (y-x) is a perfect square number, connect these two points
- Then the problem is essentially a finding the shortest path problem, which can be solved with Broad First Search

## Code

```
from collections import deque
class Solution:
def numSquares(self, n):
# create a queue
q = deque()
# store the point and number of steps to get to this point
# initially, store n, and 0 steps to get to n first
pair = (n, 0)
# append pair to queue
q.append(pair)
# loop as long as q is not empty
while q:
# check the current pair at the head of queue
curr = q.popleft()
num = curr[0]
step = curr[1]
if num == 0:
# for 0 return 0
return step
i = 1
for i in range(num - i**2 + 1):
# as long as num can hold another perfect square
pair = (num - i**2, step + 1)
q.append(pair)
```

```
```

This solution is correct logically however, it will have TLE issue. Because there were too many repetitive calculations.

## Complexity

- Time complexity is O(n**2), a nested while and for loop is used
- Space complexity is O(n), a deque is used to store node and its level info

## Optimization

Due to TLE, one way to optimize the solution is to record whether a num is visited, if it’s already visited, no need to push it into the q to avoid repetition and waste on resources.

```
from collections import deque
class Solution:
def numSquares(self, n: int) -> int:
# create a queue
q = deque()
# store the point and number of steps to get to this point
# initially, store n, and 0 steps to get to n first
pair = (n, 0)
# append pair to queue
q.append(pair)
# create a visited list, initialized with all False
visited = [False] * (n+1)
# since (n,0) is append in queue already, so n is already visited
visited[n] = True
# loop as long as q is not empty
while q:
# check the current pair at the head of queue
curr = q.popleft()
num = curr[0]
step = curr[1]
if num == 0:
# for 0 return 0
return step
i = 1
while True:
a = num - i**2
# as long as num can take another perfect square
# a is the next perfect square
if a < 0:
break
if not visited[a]:
pair = (a, step + 1)
q.append(pair)
visited[a] = True
i += 1
def test():
sol = Solution()
print(sol.numSquares(12))
print(sol.numSquares(13))
print(sol.numSquares(1))
test()
```

```
3
2
1
```

## White Board

Below is the white board: