### 279. Perfect Squares

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.``````

### Analyze

1. `5 -> 1 -> 0`;
2. `5 -> 4 -> 0`;
3. `5 -> 4 -> 3 -> 2 -> 1 -> 0`;
``````/**
* @param {number} n
* @return {number}
*/
var numSquares = function(n) {
const list = []
list.push({ num: n, step: 0 })

while (list.length > 0) {
const { num, step } = list.shift()
if (num === 0) return step
for (let i = 1; num - i * i >= 0; i++) {
list.push({ num: num - i * i, step: step + 1 })
}
}
}``````

``````/**
* @param {number} n
* @return {number}
*/
var numSquares = function(n) {
const list = []
list.push({ num: n, step: 0 })
const visitedObj = { [n]: true }
while (list.length > 0) {
const { num, step, visited } = list.shift()
for (let i = 1;; i++) {
const extraNum = num - i * i
if (extraNum < 0) break
// this line return the result in advance, it reduces perform time very much.
if (extraNum === 0) return step + 1
if (!visitedObj[extraNum]) {
visitedObj[extraNum] = true
list.push({ num: num - i * i, step: step + 1 })
}
}
}
}``````

127、126