text: Count ways to represent a number as sum of perfect squares | C ++ 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
code: #include <bits/stdc++.h> NEW_LINE using namespace std ; vector < int > psquare ; void calcPsquare ( int N ) { for ( int i = 1 ; i * i <= N ; i ++ ) psquare . push_back ( i * i ) ; } int countWays ( int index , int target ) { if ( target == 0 ) return 1 ; if ( index < 0 target < 0 ) return 0 ; int inc = countWays ( index , target - psquare [ index ] ) ; int exc = countWays ( index - 1 , target ) ; return inc + exc ; } int main ( ) { int N = 9 ; calcPsquare ( N ) ; cout << countWays ( psquare . size ( ) - 1 , N ) ; return 0 ; }