✅ Решение задачи 51

Time: O(n!)
Space: O(n)

💡 Идея
🟦Важно заметить, какие позиции ограничивает каждый новый ферзь. Например, поставив одного ферзя в клетку, можно точно сказать, что в текущие столбец и строку второго ферзя уже не поставить. Остается только учесть диагонали, но как это сделать?

🟦Введем идею с уникальными идентификаторами диагоналей:
▫Для положительной диагонали (направлена вверх, если начинать проводить слева) идентификатором служит сумма индексов строки и столбца
▫Для отрицательной диагонали (направлена вниз) — разница строки и столбца
▫Таким образом, при добавлении ферзя мы фиксируем не только его столбец, но и обе диагонали, блокируя тем самым возможность поставить туда других

🟦Получаем следующий алгоритм:
▫Для каждой клетки текущей строки проверяем возможность постановки ферзя
▫Если позиция допустима, добавляем её в решение и рекурсивно переходим к следующей строке
▫После возврата из рекурсии убираем сохранённую позицию, чтобы продолжить перебор
▫Когда доходим до последней строки и удаётся расставить всех n ферзей, преобразуем текущее состояние доски в список строк и добавляем его в итоговый результат

👩‍💻 Java Algo | #solution51

✅ Решение задачи 679

Time: O(n³ * 3^n * n!)
Space: O(n²)

💡 Идея
🟦Переводим исходный массив в список вещественных чисел для удобной работы. Затем запускаем рекурсивный метод backtrack, передавая в него этот список

🟦В методе просто перебираем все пары чисел в текущем списке и плюсом для каждой перебираем все возможные арифметические комбинации

🟦Добавляем в новый список результат комбинации и оставшиеся в старом списке числа, а затем рекурсивно вызываем backtrack для проверки текущего варианта

🟦После возврата из рекурсии, удаляем последнюю добавленную комбинацию, используя принцип backtracking для перебора всех возможных вариантов

🟦Базовым случаем является проверка на размер списка:
▫если в списке остался только один элемент, проверяется, близок ли он к 24 с погрешностью 0.1, чтобы учитывать неточности вычислений с плавающей запятой
▫если чисел больше одного, действуем по описанному алгоритму

👩‍💻 Java Algo | #solution679