> For the complete documentation index, see [llms.txt](https://zedive.gitbook.io/project-l/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://zedive.gitbook.io/project-l/part-2/dynamic_programming/knapsack/perfect-sqaures.md).

# Perfect Sqaures

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

> 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, ... 

## Examples

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

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

## Approach 

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%27s_four-square_theorem)