4m java DFS Solution


  • 0
    L
        private long ans;
        private void DFS(long n, long count){
            if (count >= ans)
                return;
            
            if (n == 0 && ans > count){
                ans = count;
                return;
            }
            
            int max = (int)Math.sqrt(n);
            for (long i = max; i >= 1; i--){
                long val = i * i * (ans - count);
                if (val < n)
                    break;
                if (i * i == n){
                    ans = Math.min(ans, count + 1);
                    break;
                }
                    
                DFS(n - i * i, count + 1);
            }
        }

Log in to reply
 

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