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, return3because12 = 4 + 4 + 4; givenn=13, return2because13 = 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))