279. Perfect Squares

class Solution:
    def numSquares(self, n: int) -> int:
        if n < 2:
            return n
        
        # populate possibles to square root of number
        max_n = int(n ** 0.5)
        possible = [x ** 2 for x in range(1, max_n + 1)]
        
        # search by subtraction
        count = 0
        to_check = {n}
        while to_check:
            count += 1
            next_step = set()
            for x in to_check:
                for y in possible:
                    if x == y:
                        return count
                    if x < y:
                        break
                    next_step.add(x - y)
            to_check = next_step

        return count