Beats 98.96%


  • 0
    S
    class Solution(object):
        def solveNQueens(self, n):
            """
            :type n: int
            :rtype: List[List[str]]
            """
            matrix = []
            res = []
            dfs(res, 0, [], set(), set(), set(),n )
            solutions = []
            for subset in res:
                sol = []
                for idx in subset:
                    sol.append("."*idx+"Q"+"."*(n-idx-1))
                solutions.append(sol)
            return solutions
    
    def dfs(res, row, path, cols, xySum, xyDif, n):
        if row == n:
            res.append(path)
            return
        for col in range(n):
            if col not in cols and (row+col) not in xySum and (row-col) not in xyDif:
                cols.add(col)
                xySum.add(row+col)
                xyDif.add(row-col)
                dfs(res, row+1, path+[col], cols, xySum, xyDif, n)
                cols.remove(col)
                xySum.remove(row+col)
                xyDif.remove(row-col)
        
        
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.