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