My 8ms DFS Java solution


  • 1
    B

    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
            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));
            }
        }
    }
    

Log in to reply
 

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