The prune strategy here:

- Skip searching further if there is no possible better solution.
- Use % to search as fast as possible.

```
public class Solution {
int ans = Integer.MAX_VALUE;
int numSquares(int n) {
numSquares(n, 0);
return ans;
}
void numSquares(int res, int level) {
// No need to search further
if(level>=ans)
return ;
if(res==0) {
ans = Math.min(ans, level);
return ;
}
//Try to search as fast as possible
for(int i=(int)Math.sqrt(res); i>=1;i--) {
numSquares(res%(i*i), level + res/(i*i));
}
}
}
```