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

``````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

``````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))``````

Last updated