# Perfect Squares

Companies:

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.
for(int i = 1; i*i <= sum; i++) {
mi = min(mi, solve(answer, sum - i*i) + 1);
}
}

}

int main() {

int n = 13;

// answer[i] will store the minimum number of perfect squares needed to make i