Why it works
- Along a ↘ diagonal r and c grow together, so r - c stays the same; along a ↙ diagonal r + c does. A queen takes its column, its r - c and its r + c, so one look into three sets tells whether a cell is attacked.
- Each call fills one row with a column no queen above attacks, so a call at r = n has a full valid board and adds exactly one way, and a row with no free column ends its branch at once.
- Each call gets new sets with its queen added, so the caller’s sets stay as they were: going back up removes the queen without any undo.
Complexity
Time O(n!) at most: row 0 has n columns to try, row 1 at most n − 1, and so on; each check is O(1) with the sets, though copying them costs O(n) per call. Memory O(n²): up to n calls deep, each with sets of up to n numbers.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗