# Perfect Sqaures

## Question ([LC.279](https://leetcode.com/problems/perfect-squares/))&#x20;

> Given an integer `n`, return _the least number of perfect square numbers that sum to_ `n`.

A **perfect square** is an integer that is the square of an integer. For example, 1, 4, 9, 16, ...&#x20;

## Examples

```
I: n = 12
O: 3 (4 + 4 + 4) 

I: n = 13
O: 2 (9 + 4)
```

## Approach&#x20;

A simple greedy approach won't work. A counter example is 12 where len(9 + 1 + 1 + 1) < len(4 + 4 + 4). The solution needs to be found recursively for each square root. We can see that some subproblems overlap here. Memoization can reduce the run time.&#x20;

## Brute Force Recursion&#x20;

```python
def numSquares(self, n: int) -> int:
    min_count = self.search_squares_helper(n)
    return min_count

def search_squares_helper(self, n: int) -> int:
    # base case
    if n == 0:
        return 0

    # recursive calls 
    float_root = math.sqrt(n)
    biggest_root = int(math.floor(float_root))

    min_count = 10001
    for root in range(biggest_root, 0, -1):
        count = 1 + self.search_squares_helper(n - root**2)
        min_count = min(count, min_count)

    return min_count
```

This is an exponential algo. TLE at n = 41.&#x20;

## Memoized Recursion&#x20;

```python
def numSquares(self, n: int) -> int:
    memo: Dict[int, int] = {}
    min_count = self.search_squares_helper(n, memo)
    return min_count

def search_squares_helper(self, n: int, memo: Dict[int, int]) -> int:
    # base case
    if n == 0:
        return 0
    
    if n in memo:
        return memo[n]

    # recursive calls
    float_root = math.sqrt(n)
    biggest_root = int(math.floor(float_root))

    min_count = 10001
    for root in range(biggest_root, 0, -1):
        count = 1 + self.search_squares_helper(n - root**2, memo)
        min_count = min(count, min_count)
    memo[n] = min_count
    
    return min_count
```

This gets the run time down to the number of subproblems which are bounded by the input value. However, recursion has some overhead. OJ gives TLE when n = 8405.&#x20;

## DP

```python
def numSquares(self, n: int) -> int:
    dp: List[int] = [10001 for i in range(n + 1)]
    
    # init
    dp[0] = 0
    dp[1] = 1
    
    # topo order 
    for i in range(2, n + 1):
        # recursive step 
        biggest_root = math.floor(math.sqrt(i))
        for root in range(1, int(biggest_root) + 1):
            dp[i] = min(dp[i], 1 + dp[i - root * root])
    
    # final answer
    return dp[n]
```

time `O(n * sqrt(n))` space `O(n)`&#x20;

## Reading&#x20;

* Wikipedia - [Lagrange's four-square theorem](https://en.wikipedia.org/wiki/Lagrange's_four-square_theorem)
