# LeetCode 279: Perfect Squares

## Problem Restatement

We are given an integer `n`.

We need to return the least number of perfect square numbers whose sum is exactly `n`.

A perfect square is a number like:

```python
1, 4, 9, 16, 25
```

because:

```python
1 = 1 * 1
4 = 2 * 2
9 = 3 * 3
16 = 4 * 4
25 = 5 * 5
```

For example, for `n = 12`, one valid sum is:

```python
12 = 4 + 4 + 4
```

So the answer is `3`.

The official statement asks for the least number of perfect square numbers that sum to `n`. It gives examples such as `12 = 4 + 4 + 4` and `13 = 4 + 9`. The constraint commonly listed for this problem is `1 <= n <= 10^4`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | An integer `n` |
| Output | The minimum count of perfect squares whose sum is `n` |
| Constraint | `1 <= n <= 10000` |
| Reuse | A square may be used more than once |

Function shape:

```python
class Solution:
    def numSquares(self, n: int) -> int:
        ...
```

## Examples

For:

```python
n = 12
```

We can write:

```python
12 = 4 + 4 + 4
```

So the answer is:

```python
3
```

For:

```python
n = 13
```

We can write:

```python
13 = 4 + 9
```

So the answer is:

```python
2
```

For:

```python
n = 1
```

We can write:

```python
1 = 1
```

So the answer is:

```python
1
```

## First Thought: Brute Force

The brute force idea is to try every combination of perfect squares.

For `n = 12`, the usable square numbers are:

```python
1, 4, 9
```

We could try subtracting one square at a time:

```python
12 - 1
12 - 4
12 - 9
```

Then recursively solve the remaining number.

For example:

```python
numSquares(12)
= 1 + min(numSquares(11), numSquares(8), numSquares(3))
```

This gives the right recurrence, but plain recursion repeats the same subproblems many times.

For example, `numSquares(8)` may be reached from several different paths.

We need to store answers for smaller numbers.

## Key Insight

Let:

```python
dp[x]
```

mean:

```python
the least number of perfect squares that sum to x
```

The base case is:

```python
dp[0] = 0
```

Zero needs zero square numbers.

For every number `x` from `1` to `n`, we try every square `s` where `s <= x`.

If we use square `s` as the last square in the sum, then the remaining amount is:

```python
x - s
```

So one candidate answer is:

```python
dp[x - s] + 1
```

We choose the minimum over all valid squares.

## Algorithm

First, compute all perfect squares up to `n`.

```python
squares = []
i = 1

while i * i <= n:
    squares.append(i * i)
    i += 1
```

Then create a DP array:

```python
dp = [0] + [float("inf")] * n
```

Now fill it from left to right.

For each value `x` from `1` to `n`:

1. Try each square `s`.
2. Stop if `s > x`.
3. Update:

```python
dp[x] = min(dp[x], dp[x - s] + 1)
```

Finally, return:

```python
dp[n]
```

## Correctness

We prove that `dp[x]` stores the least number of perfect squares needed to sum to `x`.

The base case is `dp[0] = 0`, which is correct because zero needs no numbers.

Now consider any `x > 0`.

Every valid representation of `x` as a sum of perfect squares has some last square `s`. After removing that last square, the remaining sum is `x - s`.

By the time we compute `dp[x]`, the value `dp[x - s]` has already been computed because `x - s < x`.

So the number of squares in this representation is:

```python
dp[x - s] + 1
```

The algorithm tries every possible perfect square `s <= x`, so it considers every possible choice for the last square.

It takes the minimum among these choices. Therefore `dp[x]` is the least possible number of perfect squares that sum to `x`.

By induction, this holds for every value from `0` to `n`. So `dp[n]` is the correct answer.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(n sqrt(n))` | For each number up to `n`, we try all squares up to that number |
| Space | `O(n)` | The DP array stores one answer for each value from `0` to `n` |

There are about `sqrt(n)` perfect squares up to `n`.

So the nested loops cost:

```python
n * sqrt(n)
```

## Implementation

```python
class Solution:
    def numSquares(self, n: int) -> int:
        squares = []
        i = 1

        while i * i <= n:
            squares.append(i * i)
            i += 1

        dp = [0] + [float("inf")] * n

        for x in range(1, n + 1):
            for square in squares:
                if square > x:
                    break

                dp[x] = min(dp[x], dp[x - square] + 1)

        return dp[n]
```

## Code Explanation

We first build the list of usable perfect squares:

```python
squares = []
i = 1

while i * i <= n:
    squares.append(i * i)
    i += 1
```

For `n = 12`, this gives:

```python
[1, 4, 9]
```

Then we create the DP table:

```python
dp = [0] + [float("inf")] * n
```

`dp[0]` is `0`.

Every other value starts as infinity because we have not computed it yet.

Then we compute answers for all values from `1` to `n`:

```python
for x in range(1, n + 1):
```

For each `x`, we try every square that can fit inside it:

```python
for square in squares:
    if square > x:
        break
```

If we use `square`, the remaining amount is `x - square`.

So we update the best answer:

```python
dp[x] = min(dp[x], dp[x - square] + 1)
```

At the end, `dp[n]` is the minimum number of perfect squares needed:

```python
return dp[n]
```

## Testing

```python
def test_num_squares():
    s = Solution()

    assert s.numSquares(1) == 1
    assert s.numSquares(2) == 2
    assert s.numSquares(3) == 3
    assert s.numSquares(4) == 1
    assert s.numSquares(12) == 3
    assert s.numSquares(13) == 2
    assert s.numSquares(43) == 3
    assert s.numSquares(10000) == 1

    print("all tests passed")

test_num_squares()
```

Test meaning:

| Test | Why |
|---|---|
| `n = 1` | Smallest input |
| `n = 2` | Requires `1 + 1` |
| `n = 3` | Requires `1 + 1 + 1` |
| `n = 4` | Exact square |
| `n = 12` | Standard example, `4 + 4 + 4` |
| `n = 13` | Standard example, `4 + 9` |
| `n = 43` | Uses several squares, for example `25 + 9 + 9` |
| `n = 10000` | Large exact square |