My 8ms DFS Java solution

  • 1

    The prune strategy here:

    1. Skip searching further if there is no possible better solution.
    2. 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
            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));

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.