Why it works
- Each row holds exactly one queen, so a call only chooses a column for the next row, and two queens can never share a row.
- A queen goes only where no queen above attacks it, so every full board is valid, and a branch dies as soon as a row has no free column instead of after all n queens are placed.
- The call gets a new list, queens + [c], so when it returns the caller still has its own list: going back up undoes the queen by itself.
Complexity
Time O(n!) at most: row 0 has n columns to try, row 1 at most n − 1, and so on, and each check looks at up to n queens above; cut branches make it much less in practice. Memory O(n²) besides the answer: up to n calls deep, each with its list of up to n queens.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗