# 279 Perfect Squares

Given a positive integern, find the least number of perfect square numbers (for example,`1, 4, 9, 16, ...`) which sum ton.

For example, givenn=`12`, return`3`because`12 = 4 + 4 + 4`; givenn=`13`, return`2`because`13 = 4 + 9`.

**Approach 1: DFS**

**The Idea:** Find the smallest path from root to leaf. Let squares be all the perfect squares that are less than n. Begin with the root node as n, and define all children of n to be `n-squares[i]`. Continue this process until a remainder of 0 is reached. Lagrange's four-square theorem tells us that this number will always be less than or equal to 4 (\
every natural number can be represented as the sum of four integer squares). Return the minimum path length. This is bad approach because it prioritizes the depth of the tree when it is a smarter to equally weight the branches closest to the root.

```python
class Node:
    def __init__(self, num, remainder, count):
        self.num = num
        self.remainder = remainder
        self.count = count

class Solution(object):

    def __gatherPerfectSquares(self, n):
        """
        :param n: up to <= n
        :return: List[int] of perfect squares
        """
        return [i*i for i in range(1,n+1) if i*i <= n]

    def numSquares(self, n):
        """
        :type n: int
        :rtype: int
        """

        squares = self.__gatherPerfectSquares(n)

        top = Node(n, n, 0)
        stack = [top]
        the_min = 9999

        while len(stack) > 0:
            top = stack.pop()

            # Lagrange's four-square theorem
            if top.count >= 4:
                continue

            options = [num for num in squares if num <= top.remainder]
            for opt in options:
                remainder = top.remainder - opt
                if remainder == 0:
                    the_min = min(the_min, top.count + 1)
                stack.append(Node(opt, remainder, top.count + 1))

        return the_min
```

**Approach 2: BFS**

```python
import queue

class Node:
    def __init__(self, num, remainder, count):
        self.num = num
        self.remainder = remainder
        self.count = count

class Solution(object):

    def __gatherPerfectSquares(self, n):
        """
        :param n: up to <= n
        :return: List[int] of perfect squares
        """
        return [i*i for i in range(1,n+1) if i*i <= n]

    def numSquares(self, n):
        """
        :type n: int
        :rtype: int
        """

        squares = self.__gatherPerfectSquares(n)

        q = queue.Queue()
        q.put(Node(n, n, 0))

        while not q.empty():
            front = q.get()

            # Lagrange's four-square theorem
            if front.count >= 4:
                continue

            options = [num for num in squares if num <= front.remainder]
            for opt in options:
                remainder = front.remainder - opt
                if remainder == 0:
                    return front.count + 1
                q.put(Node(opt, remainder, front.count + 1))
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://maksimdan.gitbook.io/interview-practice-problems/leetcode_sessions/279-perfect-squares.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.