Share my 9 ms c++ solution


  • 0
    X
    class Solution {
    public:
        vector<vector<string> > solveNQueens(int n) {
            vector<vector<string> > ans;
            vector<int> solution;
            for (int i=0; i<n; i++)
                    solution.push_back(i);
    
            helper(ans, solution, 0);
            return ans;
        }
    
        void helper(vector<vector<string> > &ans, vector<int> &solution, int start) {
            if (start == solution.size()) {
                    ans.push_back(vector<string>());
                    for (int i=0; i<solution.size(); i++) {
                            ans.back().push_back(string(solution.size(), '.'));
                            ans.back().back()[solution[i]] = 'Q';
                    }
                    return;
            }
    
            for (int i=start; i<solution.size(); i++) {
                    swap(solution[start], solution[i]);
                    if (isValid(solution, start)) {
                            helper(ans, solution, start+1);
                    }
                    swap(solution[start], solution[i]);
            }
    
    
        }
    
        bool isValid(vector<int> &solution, int index) {
            for (int row=index-1; row>=0; --row) {
                    if (index-row == abs(solution[index] - solution[row]))
                            return false;
            }
    
            return true;
        }
    };

Log in to reply
 

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