Задача от Google про разложение на полные квадраты
#py_basic

У этой задачи есть история. Моя знакомая (она NLP / бэкенд-разработчик) много гуглила по работе, и поисковик однажды предложил ей решить несколько задач на программирование. Оказывается, Google следит за вашими поисковыми запросами не только для того, чтобы показывать вам более релевантную контекстную рекламу. Если вы много гуглите про бэкенд-разработку, то Google может предложить вам такой челлендж. Если его успешно пройти, то дальше зовут на собеседование. Там было несколько задач, я покажу вам самую первую из них. Она не сложная, но сможете ли вы решить её эффективно?

На входе положительное целое число, нужно разложить его на сумму квадратных чисел так, чтобы слагаемых было наименьшее количество. Слагаемые-точные квадраты нужно расположить в списке в порядке убывания. Например, если нам пришло число 7, то нужно разложить его на [4, 1, 1, 1], но не на [1, 1, 1, 1, 1, 1, 1] (не наименьшее количество слагаемых), не на [5, 1, 1] (первое число не является квадратом целого числа), не на [1, 4, 1, 1] (неправильный порядок) и так далее. Ещё несколько примеров:

12 -> [9, 1, 1, 1]
16 -> [16]
1 -> [1]

Завтра покажу решение и сделаю разбор.