https://www.codewars.com/kata/54eb33e5bc1a25440d000891/train/python

ITERATIVE_Square_into_Squares_Protect_trees.py

# ITERATIVE backtracking + pruning
import math

def decompose(n):
    stk = [ [n**2, n-1] ] # "function stack", (squared, internal counter i (next number can't be larger or equal to...))
    
    while stk:
        squared, internal_counter_i = stk[-1]
        if squared == 0:
            stk.pop()
            return list(reversed( [i+1 for _,i in stk] ))
        else:
            csfi = len(stk)-1 # current stack frame index
#             min(int(math.sqrt(squared)), next_number_cannot_be_larger_than)
            stk[csfi][-1] = min(int(math.sqrt(squared)), stk[csfi][-1]) 
            appended = False
            while stk[csfi][-1] >= 1:
                if squared == 9:
                    print(stk[-1])
                sq2 = stk[csfi][-1]**2
                if squared >= sq2:
                    stk.append( [squared - sq2, stk[csfi][-1]-1] )
                    stk[csfi][-1]-=1 # the "current" stack frame is now 2 items behind
                    appended = True
                    break
                stk[csfi][-1]-=1
            if not appended: stk.pop()
    return None