My code in C++, can someone tell the complexity?


  • 0
    R

    Hi, here is my solution:
    The space complexity should be O(n), and what is the time complexity? is this O(n^(2*n)) ?

    class Solution {
    public:
        int totalNQueens(int n) {
            vector<int> cols;
            return totalNQueens(n, cols, 0);
        }
    private:
        bool possible(vector<int>& cols, int index) {
            for(int i=0; i<cols.size(); ++i){
                    if(cols[i]==index) return false;
                    if(fabs(index-cols[i])==fabs(cols.size()-i)) return false;
            }
            return true;
        }
        int totalNQueens(int n, vector<int>& cols, int num) {
            if(num==n) return 1;
            int total=0;
            for(int i=0; i<n; ++i){
                if(possible(cols, i)) {
                    cols.push_back(i);
                    cols[num]=i;
                    total+=totalNQueens(n, cols, num+1);
                    cols.pop_back();
                }
            }
            return total;
        }
    };

  • 0
    C

    Backtracking search the possible situation,so it complexity will be O(N!).


Log in to reply
 

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