Найдите все комбинации идеальных квадратов, которые в сумме дают N с дубликатами.

Для заданного положительного целого числа N задача состоит в том, чтобы напечатать все возможные суммы полных квадратов так, чтобы общая сумма всех полных квадратов была равна N.

Пример:

Input: N=8
Output: 4 4
              1 1 1 1 4
              1 1 1 1 1 1 1 1 
Explanation: There are three possible ways to make sum equal to N

Input: N=3
Output: 1 1 1

Подход: Данную проблему можно решить с помощью рекурсии и поиска с возвратом. Идея состоит в том, чтобы сгенерировать список идеальных квадратов меньше N , а затем вычислить возможные комбинации суммы идеальных квадратов, которые равны N. В рекурсивной функции по каждому индексу элемент может быть выбран для списка или не выбран. . Выполните следующие шаги, чтобы решить проблему:

• Инициализируйте ArrayList для хранения всех идеальных квадратов меньше N
• Перебрать целое число N от 1 до квадратного корня из N используя переменную я
  • Если квадрат i меньше или равен N, то добавить i * i в список
• Используйте рекурсию и поиск с возвратом, чтобы вычислить сумму идеальных квадратов, равных N
• В каждом индексе ind do следующее:
  • Не включать элемент в текущий индекс и сделать рекурсивный вызов следующего индекса
  • Включить элемент по текущему индексу и сделать рекурсивный вызов по тому же индексу
• Для рекурсивной функции потребуются следующие два базовых случая:
  • Если N становится меньше нуля или если ind достиг конца списка, верните
  • Если N становится равным нулю, то выведите список

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N * 2^N), где N — заданное число.
Вспомогательное пространство: O(N)