Leetcode 52. N-Queens II

Problem

Leetcode 52 - N-Queens II

Example:

Input: n = 4
Output: 2

Input: n = 1
Output: 1

Approach

Similar to the question Leetcode-51, we can solve this using a counter instead of array to save all the board state

Here is the Python code for the solution:

class Solution:
    def totalNQueens(self, n: int) -> int:
        col = set()
        posDiag = set()
        negDiag = set()

        res = 0
        def dfs(r):
            nonlocal res
            if r == n:
                res += 1
                return
            
            for c in range(n):
                if c in col or (r+c) in posDiag or (r-c) in negDiag:
                    continue
                
                col.add(c)
                posDiag.add(r+c)
                negDiag.add(r-c)

                dfs(r+1)

                col.remove(c)
                posDiag.remove(r+c)
                negDiag.remove(r-c)
    
        dfs(0)
        return res

Time Complexity and Space Complexity

Time Complexity: $O(n!)$

Space Complexity: $O(n)$