C++ easy backtracking, an improvement over the previous one. 3ms Solution.


  • 0
    S
    class Solution {
    public:
        bool check(int row, int col, vector<int>& history)
        {
            for (int i = 0; i < row; i++) {
                int col2 = history[i];
                if (col2 == col || row - i == abs(col2 - col))
                    return 0;
            }
            return 1;
        }
    
        void recurse(vector<int>& history, int row, int n,vector<vector<string>>& result)
        {
            for (int col = 0; col < n; col++) {
                if (check(row, col, history)) {
                    history[row] = col;
                    if (row == n-1) {
                        // Solved it.  Create a board and store it.
                        vector<string> res(n);
                        std::string x(n, '.');
                        for (int i = 0; i < n; i++) {
                            x[history[i]] = 'Q';
                            res[i] = x;
                            x[history[i]] = '.';
                        }
                        result.push_back(res);
                    } else {
                        // Go on to the next row.
                        recurse(history, row+1, n, result);
                    }
                }
            }
        }
    
        vector<vector<string>> solveNQueens(int n)
        {
            vector<vector<string>> result;
            vector<int> history(n);
            recurse(history, 0, n, result);
            return result;
        }
    };
    

Log in to reply
 

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