Clean C++ backtracking solution


  • 0
    class Solution {
    public:
        int totalNQueens(int n) {
            vector<pair<int, int>> path;
            int count = 0;
            dfs(0, n, path, count);
            
            return count;
        }
        
        void dfs(int i, int n, vector<pair<int, int>>& path, int& count){
            if(i == n){
                count++;
                return;
            }           
            for(int j = 0; j < n; j++){
                bool add = true;
                pair<int, int> candiate = make_pair(i, j);
                for(auto P: path){
                    if(isAttackable(P, candiate)){
                        add = false;
                        break;
                    }
                }
                if(add){
                    path.push_back(candiate);
                    dfs(i + 1, n, path, count);
                    path.pop_back(); 
                }
            }
        }
        
        bool isAttackable(pair<int, int> P1, pair<int, int> P2){
            if(P2.second == P1.second || abs(P2.second - P1.second) == abs(P2.first - P1.first)) return true;
            return false;
        }
    };

  • 0

    nice solution


Log in to reply
 

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