```
public class Solution {
public int numSquares(int n) {
Queue<Integer> queue = new LinkedList<>();
Set<Integer> set = new HashSet<>();
int step = 0;
queue.offer(n);
while (!queue.isEmpty()) {
int size = queue.size();
step++;
for (int i = 0; i < size; i++) {
int curr = queue.poll();
if (!set.add(curr)) continue;
for (int j = 1; j <= Math.sqrt(curr); j++) {
int next = curr - j * j;
if (next == 0) return step;
queue.offer(next);
}
}
}
return 0;
}
}
```