算法题：N皇后-2

描述：

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回 n 皇后问题 不同的解决方案的数量。

链接：https://leetcode-cn.com/problems/n-queens-ii

思路

DFS + 回溯，添加元素前先判断是否合法

代码

class Solution {
public:
    int res = 0;
    int totalNQueens(int n) {
        vector<int> places;
        dfs(places, n);
        return res;
    }

    void dfs(vector<int>& places, int n) {
        if (places.size() == n) {
            res++;
            return;
        }
        for (int i = 0;i < n;i++) {
            if (isValid(places, i)) {
                places.push_back(i);
                dfs(places, n);
                places.pop_back();
            }
        }
    }

    bool isValid(vector<int>& places, int x) {
        const int n = places.size();
        for (int i = 0;i < n;i++) {
            if (places[i] == x || x - places[i] == n - i || places[i] - x == n - i) return false;
        }
        return true;
    }
};

复杂度
时间复杂度：O(n^2)
空间复杂度：O(n)