Count ways to represent a number as sum of perfect squares | Java program for the above approach ; Store perfect squares less than or equal to N ; Utility function to calculate perfect squares less than or equal to N ; Function to find the number of ways to represent a number as sum of perfect squares ; Handle the base cases ; Include the i - th index element ; Exclude the i - th index element ; Return the result ; Driver Code ; Given Input ; Precalculate perfect squares <= N ; Function Call
import java . io . * ; import java . lang . * ; import java . util . * ; public class GFG { static ArrayList < Integer > psquare = new ArrayList < > ( ) ; static void calcPsquare ( int N ) { for ( int i = 1 ; i * i <= N ; i ++ ) psquare . add ( i * i ) ; } static int countWays ( int index , int target ) { if ( target == 0 ) return 1 ; if ( index < 0 target < 0 ) return 0 ; int inc = countWays ( index , target - psquare . get ( index ) ) ; int exc = countWays ( index - 1 , target ) ; return inc + exc ; } public static void main ( String [ ] args ) { int N = 9 ; calcPsquare ( N ) ; System . out . print ( countWays ( psquare . size ( ) - 1 , N ) ) ; } }