Solving Perfect Squares problem using breadth-first search

I was learning recently about solving problems that use breadth-first search (BFS). This is a family of computer science algorithms that traverse tree data structures “by levels”. That is, starting at the root, we process all nodes on level 1, then all nodes on level 2, etc.

One typical application of BFS is to find the shortest path between the root and the given nodes.

To implement BFS, one should use the queue data structure.

The schema of the algorithm is the following (in pseudocode mixture of C and Python):

Given: root node, target node

add the root node to the queue

level = 0
while queue is not empty:
    # iterate over the nodes that are on the same level.
    size = queue.size()
    for (i = 0; i < size; i++):
        curr = pop the first node from the queue

        if curr is the target node, then return level

        add all neighbors of curr to the queue

    level++

return -1

Note that we return value of the level variable, when the currently processed node is the given target. If this condition is not met during the tree traversal, we return -1.

An example of the problem that can be solved using BFS is the Perfect Squares problem.

The statement of the problem is to find the minimal number of perfect squares that sum up to the given number n. The perfect square is an integer that is a square of another integer, for example, \(9 = 3^2\), therefore, 9 is the perfect square. So, if n is 13, the answer is 2 as \(13 = 9 + 4\).

The solution in Python using BFS is the following.

import math
from collections import deque


def min_num_of_squares(n: int) -> int:
    squares = []
    i = 1
    while i**2 <= n:
        squares.append(i**2)
        i += 1

    # Initialize the queue with root node `0`.
    queue = deque([0])
    # We need at least one summand in the sum of squares to get `n`.
    step = 1

    while queue:
        # Process elements of the queue from the same level.
        # Note that, although `len(queue)` is dynamic,
        # when we initialize `range`, it is fixed, that is,
        # `range` will not be affected by the changes
        # of the queue length while processing nodes
        # of the same level.
        for __ in range(len(queue)):
            curr = queue.popleft()

            # Process potential squares of the `curr` node.
            for sq in squares:
                if curr + sq == n:
                    return step
                if curr + sq > n:
                    break
                if curr + sq < n:
                    queue.append(curr + sq)

        step += 1

    return -1

Breadth-first search approach to this problem visually can be thought of as the root node “zero” at the center, surrounded by “circles” of perfect squares. And the solution is the minimal number of such “circles” that we need to draw, such that there is a sum of numbers that gives n. In practice, the “circles” are incomplete as we do not have to process elements that lead the sum to exceed the given number n.

• programming
• algorithms