Minimum number of squares whose sum equals to given number n | A naive recursive JAVA program to find minimum number of squares whose sum is equal to a given number ; Returns count of minimum squares that sum to n ; base cases ; getMinSquares rest of the table using recursive formula Maximum squares required is ; n ( 1 * 1 + 1 * 1 + . . ) Go through all smaller numbers to recursively find minimum ; Driver code
class squares { static int getMinSquares ( int n ) { if ( n <= 3 ) return n ; int res = n ; for ( int x = 1 ; x <= n ; x ++ ) { int temp = x * x ; if ( temp > n ) break ; else res = Math . min ( res , 1 + getMinSquares ( n - temp ) ) ; } return res ; } public static void main ( String args [ ] ) { System . out . println ( getMinSquares ( 6 ) ) ; } }