Генераторы квадратов

Раз сумма без любого слагаемого - полный квадрат, в качестве слагаемых можно использовать только числа вида n - x*x для целых x, обозначим их как b[1], b[2], …, b[t] Таких чисел порядка квадратного корня из n.
 
Надо почитать число способов представить n в виде суммы k слагаемых, каждое из заданного массива b.

Можно воспользоваться опять рекурсивным перебором вариантов.

def search(x, n, k, prefix):
    if k == 1:
        if n > prefix[-1] and n in terms_set:
            print("YES")
            print(*(prefix + [n]))
            exit(0)
        return
    if x == len(terms) or terms[x] * k > n:
        return
    search(x + 1, n - terms[x], k - 1, prefix + [terms[x]])
    search(x + 1, n, k, prefix)


n, k = map(int, input().split())
terms = []
for x in range(1, n):
    if x * x >= n:
        break
    terms.append(n - x * x)
terms.sort()
terms_set = set(terms)
search(0, n, k, [])
print("NO")