Question

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.

Example 1:

Input: n = 12
Output: 3
Explanation: 12 = 4 + 4 + 4.

Example 2:

Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.

BFS Solution

Populate numbers that can be summed with 1, 2, 3, … perfect square numbers. It also uses an array to store results for 1, 2, …, n so it’s sort of a DP solution too.

from collections import deque
class Solution(object):
    def numSquares(self, n):
        """
        :type n: int
        :rtype: int
        """
        perfectSqrs = list()
        i = 0
        while i * i <= n:
            perfectSqrs.append(i * i)
            i += 1

        counts = [0] * (n + 1)
        q = deque()
        count = 1

        for sqr in perfectSqrs:
            counts[sqr] = count
            q.append(sqr)

        if counts[-1] == 1:
            return 1

        while True:
            newQ = deque()
            count += 1
            while len(q) > 0:
                m = q.popleft()
                for sqr in perfectSqrs:
                    s = m + sqr
                    if s < n and counts[s] == 0:
                        counts[s] = count
                        newQ.append(s)
                    elif s == n:
                        return count
                    elif s > n:
                        break
            q = newQ