leetcode：面试题 08.12. 八皇后【dfs + backtrack】

分析

定义一个函数生成当前queens的结果
然后queens用来记录每行的queen分别在什么位置
backtrack用来记录当前第i行的queen的位置在哪
如果当前i = n就可以加入最终的结果了
否则开始遍历每个j，如果当前的ij满足cols diag1 和 diag2就可以取这个j
然后设定queen 并加入三个set
然后dfs下一层 再回溯为之前的set 再遍历下一个j

ac code

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        # backtrack + set
        row = ['.'] * n
        queens = [-1] * n
        cols, diag1, diag2 = set(), set(), set()
        ans = []

        def generateBoard():
            board = []
            for i in range(n):
                row[queens[i]] = 'Q'
                board.append(''.join(row))
                row[queens[i]] = '.'
            return board
        
        def backtrack(i):
            if i == n:
                ans.append(generateBoard())
            else:
                # next row which col
                for j in range(n):
                    if j in cols or i + j in diag1 or i - j in diag2:
                        continue
                    # dfs + backtrack
                    queens[i] = j
                    cols.add(j)
                    diag1.add(i + j)
                    diag2.add(i - j)
                    backtrack(i + 1)
                    cols.remove(j)
                    diag1.remove(i + j)
                    diag2.remove(i - j)
        
        backtrack(0)
        return ans

总结

dfs + backtrack的复杂度并不是n的n次方 中间剪枝了不少的
复杂度是o(N!)