- Mathematical, maths-perfect-square, Recursion, Searching

Count ways to represent a number as sum of perfect squares

Count ways to represent a number as sum of perfect squaresGiven an integer N, the task is to find the number of ways to represent the number N as sum of perfect squares.Examples:Input: N = 9Output: 4Explanation:There are four ways to represent 9 as the sum of perfect squares:1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 = 91 + 1 + 1 + 1 + 1 + 4 = 91 + 4 + 4 = 99 = 9Input: N = 8Output: 3Naive Approach: The idea is to store all the perfect squares less than or equal to N in an array. The problem now reduces to finding the ways to sum to N using array elements with repetition allowed which can be solved using recursion. Follow the steps below to solve the problem:Store all the perfect squares less than or equal to N and in an array psquare[].Create a recursion function countWays(index, target) that takes two parameters index, (initially N-1) and target (initially N):Handle the base cases:If the target is 0, return 1.If either index or target is less than 0, return 0.Otherwise, include the element, psquare[index] in the sum by subtracting it from the target and recursively calling for the remaining value of target.Exclude the element, psquare[index] from the sum by moving to the next index and recursively calling for the same value of target.Return the sum obtained by including and excluding the element.Print the value of countWays(N-1, N) as the result.Below is the implementation of the above approach:C++#include using namespace std;  vector psquare;  void calcPsquare(int N){    for (int i = 1; i * i