Почему это работает
- В каждой строке ровно один ферзь, поэтому вызов выбирает только столбец для следующей строки, и два ферзя не окажутся в одной строке.
- Ферзь встаёт только туда, где его не бьёт никто сверху, поэтому каждая полная доска верна, а ветка обрывается, как только в строке нет свободного столбца, а не после расстановки всех n ферзей.
- Вызов получает новый список, queens + [c], поэтому, когда он возвращается, у вызывающего остаётся свой список: подъём сам отменяет ферзя.
Сложность
Время не больше O(n!): в строке 0 можно попробовать n столбцов, в строке 1 не больше n − 1 и так далее, а каждая проверка смотрит до n ферзей сверху; отрезанные ветки на деле дают гораздо меньше. Память O(n²) помимо ответа: глубина до n вызовов, у каждого свой список до n ферзей.
дальшеТеперь реши её сам, без подсказок.
Решить на LeetCode ↗