```
public class Solution {
public int numSquares(int n) {
int init = (int)Math.sqrt(n);
search(n, 0, 0, init);
return min;
}
private int min = Integer.MAX_VALUE;
private void search(int target, int sum, int depth, int n) {
// if the least number of perfect square numbers is greater than the min value, we don't need to go deeper
if (depth > min) return;
if (target == sum) {
min = Math.min(min, depth);
return;
} else if (target < sum) return;
for (; n > 0; n--) {
int temp = n * n;
sum += temp;
search(target, sum, depth + 1, n);
sum -= temp;
}
}
}
```