Given a positive integer ` n `

, find the least number of perfect squares which sum to ` n `

## Example Test Cases

### Sample Test Case 1

Input grid: ` 5 `

Expected Output: ` 2 `

Explanation: We need minimum two perfect squares to sum up to 5. for example, 5 can be written as ` 5 = 1`

^{2}` + 2`

^{2}` `

### Sample Test Case 2

Input grid: ` 12 `

Expected Output: ` 3 `

Explanation: You need minimum of three perfect squares to write 12: ` 12 = 2`

^{2}` + 2`

^{2}` + 2`

^{2}` `

## Solution

We can solve this problem by using recursion and then memoizing the results.

Let ` f(n) `

be the minimum number of perfect squares needed to form ` n `

.

Therefore, we can write ` f(n) = min(f(n - 1`

^{2}`), f(n - 2`

^{2}`), f(n - 3`

^{2}`), f(n - 4`

^{2}`),....f(n - i`

^{2}`)) + 1; for all i such that i`

^{2}` < n `

Since, we might end up computing this function again and again for same numbers, we can memoize the results and store it in an array/map as shown below in the implementation.

## Solution Implementation

#include <bits/stdc++.h> using namespace std; int solve(vector& answer, int sum) { int mi = INT_MAX; // If the answer[sum] is not computed, compute it. if (answer[sum] < 0) { for(int i = 1; i*i <= sum; i++) { mi = min(mi, solve(answer, sum - i*i) + 1); } answer[sum] = mi; } return answer[sum]; } int main() { int n = 13; // answer[i] will store the minimum number of perfect squares needed to make i vector answer(n + 1); // if answer[i] is -1, it means that we have not computed answer[i] before. fill(answer.begin(), answer.end(), -1); // Since, the number of ways of forming 0 with perfect squares is 0 answer[0] = 0; cout << "The minimum perfect squares needed are " << solve(answer, n) << "\n"; }