N-Queens II (Count Solutions)

🎯

N-Queens II (Count Solutions)

hardBACKTRACKINGAmazonGoogle

Imagine placing queens on a chessboard so that none can attack each other, and you want to know how many ways this can be done without listing them all.

💡 This problem is a classic example of backtracking where the challenge is to explore all valid configurations efficiently. Beginners often struggle because the search space grows exponentially and pruning invalid states early is crucial.

📋

Problem Statement

Given an integer n, return the number of distinct solutions to the n-queens puzzle. The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

1 ≤ n ≤ 14The output fits in a 32-bit integer

💡

Example

Input"4"

Output2

There are two distinct ways to place 4 queens on a 4x4 board so that none attack each other.

Input"1"

Output1

Only one queen on a 1x1 board, so one solution.

• n = 1 → 1 solution
• n = 2 → 0 solutions (no valid placements)
• n = 3 → 0 solutions (no valid placements)
• n = 14 → large input to test performance and pruning

⚠️

Common Mistakes

Not checking diagonal conflicts correctly

Incorrect solutions counted or missed

✅ Check both positive and negative diagonals using row+col and row-col

Modifying shared state without backtracking

Incorrect counts due to state pollution

✅ Always undo changes (remove queen) after recursive calls

Using inefficient conflict checks scanning all previous rows

Solution too slow for larger n

✅ Use sets or bitmasks to check conflicts in O(1)

Not handling base case correctly

Missed counting valid solutions or infinite recursion

✅ Return count when row == n

Bitmask overflow or incorrect bit shifts

Wrong results or runtime errors

✅ Ensure bit operations are within integer limits and shifts are correct

🧠

Brute Force (Pure Recursion with Board Validation)

💡 Starting with brute force helps understand the problem's exponential search space and the importance of pruning invalid states early.

Intuition

Try placing a queen in every column of the current row and recursively attempt to place queens in subsequent rows, checking for conflicts each time.

Algorithm

1. Start from the first row and try placing a queen in each column.
2. For each placement, check if it conflicts with previously placed queens.
3. If no conflict, move to the next row and repeat.
4. If all queens are placed successfully, increment the solution count.

💡 The challenge is to systematically explore all placements and backtrack when conflicts arise, which is the essence of backtracking.

</>

Code

class Solution:
    def totalNQueens(self, n: int) -> int:
        def is_safe(row, col):
            for r in range(row):
                c = queens[r]
                if c == col or abs(c - col) == abs(r - row):
                    return False
            return True

        def backtrack(row):
            if row == n:
                return 1
            count = 0
            for col in range(n):
                if is_safe(row, col):
                    queens[row] = col
                    count += backtrack(row + 1)
            return count

        queens = [-1] * n
        return backtrack(0)

# Driver code
if __name__ == '__main__':
    sol = Solution()
    print(sol.totalNQueens(4))  # Output: 2

Line Notes

def is_safe(row, col):Defines a helper to check if placing a queen at (row, col) is valid

for r in range(row):Iterates over previously placed queens to check conflicts

if c == col or abs(c - col) == abs(r - row):Checks same column or diagonal conflicts

if row == n:Base case: all queens placed successfully

for col in range(n):Try placing queen in each column of current row

queens[row] = colRecord queen's position for current row

count += backtrack(row + 1)Recurse to next row and accumulate valid solutions

queens = [-1] * nInitialize queen positions with invalid column

public class Solution {
    private int count = 0;
    public int totalNQueens(int n) {
        int[] queens = new int[n];
        backtrack(0, n, queens);
        return count;
    }
    private void backtrack(int row, int n, int[] queens) {
        if (row == n) {
            count++;
            return;
        }
        for (int col = 0; col < n; col++) {
            if (isSafe(row, col, queens)) {
                queens[row] = col;
                backtrack(row + 1, n, queens);
            }
        }
    }
    private boolean isSafe(int row, int col, int[] queens) {
        for (int r = 0; r < row; r++) {
            int c = queens[r];
            if (c == col || Math.abs(c - col) == Math.abs(r - row)) {
                return false;
            }
        }
        return true;
    }

    // Driver code
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.totalNQueens(4)); // Output: 2
    }
}

Line Notes

private int count = 0;Stores total number of valid solutions

int[] queens = new int[n];Array to track queen positions by row

if (row == n)Base case: all queens placed

for (int col = 0; col < n; col++)Try each column in current row

if (isSafe(row, col, queens))Check if placing queen is valid

queens[row] = col;Place queen at current row and column

backtrack(row + 1, n, queens);Recurse to next row

for (int r = 0; r < row; r++)Check conflicts with previously placed queens

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

class Solution {
public:
    int totalNQueens(int n) {
        vector<int> queens(n, -1);
        return backtrack(0, n, queens);
    }
private:
    bool isSafe(int row, int col, const vector<int>& queens) {
        for (int r = 0; r < row; r++) {
            int c = queens[r];
            if (c == col || abs(c - col) == abs(r - row))
                return false;
        }
        return true;
    }
    int backtrack(int row, int n, vector<int>& queens) {
        if (row == n) return 1;
        int count = 0;
        for (int col = 0; col < n; col++) {
            if (isSafe(row, col, queens)) {
                queens[row] = col;
                count += backtrack(row + 1, n, queens);
            }
        }
        return count;
    }
};

int main() {
    Solution sol;
    cout << sol.totalNQueens(4) << endl; // Output: 2
    return 0;
}

Line Notes

vector<int> queens(n, -1);Initialize queen positions with invalid column

if (row == n) return 1;Base case: all queens placed successfully

for (int col = 0; col < n; col++)Try placing queen in each column

if (isSafe(row, col, queens))Check if current placement is valid

count += backtrack(row + 1, n, queens);Recurse to next row and accumulate solutions

for (int r = 0; r < row; r++)Check conflicts with previously placed queens

int c = queens[r];Get column of queen in previous row

abs(c - col) == abs(r - row)Check diagonal conflicts

var totalNQueens = function(n) {
    const queens = new Array(n).fill(-1);
    function isSafe(row, col) {
        for (let r = 0; r < row; r++) {
            const c = queens[r];
            if (c === col || Math.abs(c - col) === Math.abs(r - row)) {
                return false;
            }
        }
        return true;
    }
    function backtrack(row) {
        if (row === n) return 1;
        let count = 0;
        for (let col = 0; col < n; col++) {
            if (isSafe(row, col)) {
                queens[row] = col;
                count += backtrack(row + 1);
            }
        }
        return count;
    }
    return backtrack(0);
};

// Driver code
console.log(totalNQueens(4)); // Output: 2

Line Notes

const queens = new Array(n).fill(-1);Initialize queen positions with invalid column

if (row === n) return 1;Base case: all queens placed successfully

for (let col = 0; col < n; col++)Try placing queen in each column

if (isSafe(row, col))Check if current placement is valid

count += backtrack(row + 1);Recurse to next row and accumulate solutions

for (let r = 0; r < row; r++)Check conflicts with previously placed queens

const c = queens[r];Get column of queen in previous row

Math.abs(c - col) === Math.abs(r - row)Check diagonal conflicts

⏱

Complexity

TimeO(n!)

SpaceO(n)

Each row tries n columns, but pruning reduces the search space to roughly n! permutations.

💡 For n=8, this means about 40,000 operations, which is borderline but still feasible; for n=14, it becomes impractical.

Interview Verdict: TLE for large n

This approach is too slow for large boards but is essential to understand the problem and backtracking basics.

🧠

Backtracking with Hash Sets for Conflict Checking

💡 Using hash sets to track columns and diagonals speeds up conflict checking, reducing repeated scanning of previous rows.

Intuition

Instead of scanning all previous rows for conflicts, maintain sets of occupied columns and diagonals to check conflicts in O(1).

Algorithm

1. Initialize sets to track columns, positive diagonals, and negative diagonals under attack.
2. For each row, try placing a queen in columns not in the attacked sets.
3. If safe, add the column and diagonals to the sets and recurse to next row.
4. Backtrack by removing the queen and updating sets accordingly.
5. Count solutions when all rows are processed.

💡 This approach avoids scanning all previous queens by using sets, making conflict checks much faster.

</>

Code

class Solution:
    def totalNQueens(self, n: int) -> int:
        cols = set()
        pos_diags = set()  # r + c
        neg_diags = set()  # r - c

        def backtrack(row):
            if row == n:
                return 1
            count = 0
            for col in range(n):
                if col in cols or (row + col) in pos_diags or (row - col) in neg_diags:
                    continue
                cols.add(col)
                pos_diags.add(row + col)
                neg_diags.add(row - col)
                count += backtrack(row + 1)
                cols.remove(col)
                pos_diags.remove(row + col)
                neg_diags.remove(row - col)
            return count

        return backtrack(0)

# Driver code
if __name__ == '__main__':
    sol = Solution()
    print(sol.totalNQueens(4))  # Output: 2

Line Notes

cols = set()Tracks columns already occupied by queens

pos_diags = set() # r + cTracks positive diagonals under attack

neg_diags = set() # r - cTracks negative diagonals under attack

if col in cols or (row + col) in pos_diags or (row - col) in neg_diags:Skip if placing queen causes conflict

cols.add(col)Mark column as occupied

pos_diags.add(row + col)Mark positive diagonal as occupied

neg_diags.add(row - col)Mark negative diagonal as occupied

cols.remove(col)Backtrack: unmark column

return backtrack(0)Start backtracking from first row

import java.util.HashSet;

public class Solution {
    private int count = 0;
    public int totalNQueens(int n) {
        HashSet<Integer> cols = new HashSet<>();
        HashSet<Integer> posDiags = new HashSet<>(); // r + c
        HashSet<Integer> negDiags = new HashSet<>(); // r - c
        backtrack(0, n, cols, posDiags, negDiags);
        return count;
    }
    private void backtrack(int row, int n, HashSet<Integer> cols, HashSet<Integer> posDiags, HashSet<Integer> negDiags) {
        if (row == n) {
            count++;
            return;
        }
        for (int col = 0; col < n; col++) {
            if (cols.contains(col) || posDiags.contains(row + col) || negDiags.contains(row - col))
                continue;
            cols.add(col);
            posDiags.add(row + col);
            negDiags.add(row - col);
            backtrack(row + 1, n, cols, posDiags, negDiags);
            cols.remove(col);
            posDiags.remove(row + col);
            negDiags.remove(row - col);
        }
    }

    // Driver code
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.totalNQueens(4)); // Output: 2
    }
}

Line Notes

HashSet<Integer> cols = new HashSet<>();Tracks occupied columns

HashSet<Integer> posDiags = new HashSet<>();Tracks positive diagonals under attack

HashSet<Integer> negDiags = new HashSet<>();Tracks negative diagonals under attack

if (cols.contains(col) || posDiags.contains(row + col) || negDiags.contains(row - col))Skip invalid placements

cols.add(col);Mark column as occupied

posDiags.add(row + col);Mark positive diagonal as occupied

negDiags.add(row - col);Mark negative diagonal as occupied

cols.remove(col);Backtrack: unmark column

#include <iostream>
#include <unordered_set>
#include <vector>
using namespace std;

class Solution {
public:
    int totalNQueens(int n) {
        unordered_set<int> cols, posDiags, negDiags;
        return backtrack(0, n, cols, posDiags, negDiags);
    }
private:
    int backtrack(int row, int n, unordered_set<int>& cols, unordered_set<int>& posDiags, unordered_set<int>& negDiags) {
        if (row == n) return 1;
        int count = 0;
        for (int col = 0; col < n; col++) {
            if (cols.count(col) || posDiags.count(row + col) || negDiags.count(row - col))
                continue;
            cols.insert(col);
            posDiags.insert(row + col);
            negDiags.insert(row - col);
            count += backtrack(row + 1, n, cols, posDiags, negDiags);
            cols.erase(col);
            posDiags.erase(row + col);
            negDiags.erase(row - col);
        }
        return count;
    }
};

int main() {
    Solution sol;
    cout << sol.totalNQueens(4) << endl; // Output: 2
    return 0;
}

Line Notes

unordered_set<int> cols, posDiags, negDiags;Sets to track attacked columns and diagonals

if (cols.count(col) || posDiags.count(row + col) || negDiags.count(row - col))Skip invalid queen placements

cols.insert(col);Mark column as occupied

posDiags.insert(row + col);Mark positive diagonal as occupied

negDiags.insert(row - col);Mark negative diagonal as occupied

cols.erase(col);Backtrack: unmark column

return backtrack(0, n, cols, posDiags, negDiags);Start backtracking from first row

if (row == n) return 1;Base case: all queens placed

var totalNQueens = function(n) {
    const cols = new Set();
    const posDiags = new Set(); // r + c
    const negDiags = new Set(); // r - c

    function backtrack(row) {
        if (row === n) return 1;
        let count = 0;
        for (let col = 0; col < n; col++) {
            if (cols.has(col) || posDiags.has(row + col) || negDiags.has(row - col)) continue;
            cols.add(col);
            posDiags.add(row + col);
            negDiags.add(row - col);
            count += backtrack(row + 1);
            cols.delete(col);
            posDiags.delete(row + col);
            negDiags.delete(row - col);
        }
        return count;
    }

    return backtrack(0);
};

// Driver code
console.log(totalNQueens(4)); // Output: 2

Line Notes

const cols = new Set();Tracks occupied columns

const posDiags = new Set();Tracks positive diagonals under attack

const negDiags = new Set();Tracks negative diagonals under attack

if (cols.has(col) || posDiags.has(row + col) || negDiags.has(row - col))Skip invalid queen placements

cols.add(col);Mark column as occupied

posDiags.add(row + col);Mark positive diagonal as occupied

negDiags.add(row - col);Mark negative diagonal as occupied

cols.delete(col);Backtrack: unmark column

⏱

Complexity

TimeO(n!)

SpaceO(n)

Conflict checks are O(1) due to sets, but the search space remains factorial in n.

💡 This optimization makes the solution practical for n up to around 14, which is the problem constraint.

Interview Verdict: Accepted

This approach is efficient enough for the problem constraints and is a common interview solution.

🧠

Backtracking with Bitmask Optimization

💡 Using bitmasks to represent columns and diagonals reduces memory and speeds up conflict checks, enabling very fast pruning.

Intuition

Represent columns and diagonals as bits in integers; use bitwise operations to quickly check and update attacked positions.

Algorithm

1. Use three integers to track columns, positive diagonals, and negative diagonals under attack.
2. At each row, compute available positions by bitwise negation and AND with mask.
3. Iterate over each available position by extracting the rightmost set bit.
4. Place queen by updating bitmasks and recurse to next row.
5. Backtrack by restoring bitmasks; count solutions when all rows are placed.

💡 Bitmasking allows constant-time conflict checks and efficient iteration over valid positions, drastically reducing overhead.

</>

Code

class Solution:
    def totalNQueens(self, n: int) -> int:
        def backtrack(row, cols, pos_diags, neg_diags):
            if row == n:
                return 1
            count = 0
            available_positions = ((1 << n) - 1) & ~(cols | pos_diags | neg_diags)
            while available_positions:
                position = available_positions & -available_positions  # rightmost 1-bit
                available_positions &= available_positions - 1  # remove rightmost 1-bit
                count += backtrack(row + 1,
                                   cols | position,
                                   (pos_diags | position) << 1,
                                   (neg_diags | position) >> 1)
            return count

        return backtrack(0, 0, 0, 0)

# Driver code
if __name__ == '__main__':
    sol = Solution()
    print(sol.totalNQueens(4))  # Output: 2

Line Notes

available_positions = ((1 << n) - 1) & ~(cols | pos_diags | neg_diags)Calculate all free columns for current row

position = available_positions & -available_positionsExtract rightmost available position to try

available_positions &= available_positions - 1Remove the tried position from available positions

count += backtrack(row + 1, cols | position, (pos_diags | position) << 1, (neg_diags | position) >> 1)Recurse with updated attacked positions

if row == n:Base case: all queens placed

return backtrack(0, 0, 0, 0)Start recursion with empty board

public class Solution {
    private int count = 0;
    public int totalNQueens(int n) {
        backtrack(n, 0, 0, 0, 0);
        return count;
    }
    private void backtrack(int n, int row, int cols, int posDiags, int negDiags) {
        if (row == n) {
            count++;
            return;
        }
        int availablePositions = ((1 << n) - 1) & ~(cols | posDiags | negDiags);
        while (availablePositions != 0) {
            int position = availablePositions & (-availablePositions);
            availablePositions &= availablePositions - 1;
            backtrack(n, row + 1, cols | position, (posDiags | position) << 1, (negDiags | position) >> 1);
        }
    }

    // Driver code
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.totalNQueens(4)); // Output: 2
    }
}

Line Notes

int availablePositions = ((1 << n) - 1) & ~(cols | posDiags | negDiags);Calculate free columns for current row

int position = availablePositions & (-availablePositions);Extract rightmost available position

availablePositions &= availablePositions - 1;Remove tried position

backtrack(n, row + 1, cols | position, (posDiags | position) << 1, (negDiags | position) >> 1);Recurse with updated attacked positions

if (row == n)Base case: all queens placed

count++Increment solution count

#include <iostream>
using namespace std;

class Solution {
public:
    int count = 0;
    int totalNQueens(int n) {
        backtrack(n, 0, 0, 0, 0);
        return count;
    }
private:
    void backtrack(int n, int row, int cols, int posDiags, int negDiags) {
        if (row == n) {
            count++;
            return;
        }
        int availablePositions = ((1 << n) - 1) & ~(cols | posDiags | negDiags);
        while (availablePositions) {
            int position = availablePositions & (-availablePositions);
            availablePositions &= availablePositions - 1;
            backtrack(n, row + 1, cols | position, (posDiags | position) << 1, (negDiags | position) >> 1);
        }
    }
};

int main() {
    Solution sol;
    cout << sol.totalNQueens(4) << endl; // Output: 2
    return 0;
}

Line Notes

int availablePositions = ((1 << n) - 1) & ~(cols | posDiags | negDiags);Calculate free columns for current row

int position = availablePositions & (-availablePositions);Extract rightmost available position

availablePositions &= availablePositions - 1;Remove tried position

backtrack(n, row + 1, cols | position, (posDiags | position) << 1, (negDiags | position) >> 1);Recurse with updated attacked positions

if (row == n)Base case: all queens placed

count++Increment solution count

var totalNQueens = function(n) {
    let count = 0;
    function backtrack(row, cols, posDiags, negDiags) {
        if (row === n) {
            count++;
            return;
        }
        let availablePositions = ((1 << n) - 1) & ~(cols | posDiags | negDiags);
        while (availablePositions) {
            let position = availablePositions & (-availablePositions);
            availablePositions &= availablePositions - 1;
            backtrack(row + 1, cols | position, (posDiags | position) << 1, (negDiags | position) >> 1);
        }
    }
    backtrack(0, 0, 0, 0);
    return count;
};

// Driver code
console.log(totalNQueens(4)); // Output: 2

Line Notes

let availablePositions = ((1 << n) - 1) & ~(cols | posDiags | negDiags);Calculate free columns for current row

let position = availablePositions & (-availablePositions);Extract rightmost available position

availablePositions &= availablePositions - 1;Remove tried position

backtrack(row + 1, cols | position, (posDiags | position) << 1, (negDiags | position) >> 1);Recurse with updated attacked positions

if (row === n)Base case: all queens placed

count++Increment solution count

⏱

Complexity

TimeO(n!)

SpaceO(n)

Bitmasking reduces overhead of conflict checks to O(1), but the search space remains factorial.

💡 This approach is the fastest practical solution for n up to 14, the problem's upper limit.

Interview Verdict: Accepted

This is the optimal approach for this problem and is often expected in high-level interviews.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, approach 2 or 3 is usually best to code; approach 1 is good to explain but not to implement fully.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n!)	O(n)	Yes (deep recursion)	Yes	Mention only - never code
2. Backtracking with Sets	O(n!)	O(n)	Yes	Yes	Code this for clarity and efficiency
3. Bitmask Optimization	O(n!)	O(n)	Yes	Yes	Code this for optimal performance if comfortable with bit operations

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding all approaches, and prepare to explain tradeoffs clearly in interviews.

How to Present

Step 1: Clarify the problem and constraints.Step 2: Describe the brute force approach to show understanding of the problem.Step 3: Optimize conflict checking using sets for faster pruning.Step 4: Present bitmask optimization for maximum efficiency.Step 5: Code the chosen approach and test with examples.

Time Allocation

Clarify: 2min → Approach: 5min → Code: 10min → Test: 3min. Total ~20min

What the Interviewer Tests

The interviewer tests your understanding of backtracking, pruning invalid states, and optimizing conflict checks to handle large inputs efficiently.

Common Follow-ups

• How would you print all solutions instead of counting? → Modify to store board states.
• Can you optimize space usage? → Use bitmasking to reduce memory.
• What if n is very large? → Problem becomes infeasible; discuss heuristics or approximations.
• How to handle symmetry to reduce computations? → Prune symmetric solutions by fixing first queen.

💡 These follow-ups test your ability to adapt the solution, optimize further, and understand problem variations.

🔍

Pattern Recognition

When to Use

1) Problem involves placing items on a grid with constraints; 2) Need to explore all valid configurations; 3) Constraints involve rows, columns, diagonals; 4) Counting or listing solutions.

Signature Phrases

place n queensno two queens attackcount distinct solutions

NOT This Pattern When

Problems that only require greedy or DP without backtracking, e.g., longest increasing subsequence.

Similar Problems

N-Queens I - prints all solutions instead of countingSudoku Solver - similar constraint satisfaction on gridWord Search II - backtracking with pruning on grid

Practice

1. Consider the following Python code snippet implementing the optimal backtracking approach for Expression Add Operators. Given input num = "123" and target = 6, what is the content of the result list after the function completes?

from typing import List

def addOperators(num: str, target: int) -> List[str]:
    res = []
    path = []
    def backtrack(index: int, evaluated: int, last_operand: int):
        if index == len(num):
            if evaluated == target:
                res.append(''.join(path))
            return
        for i in range(index, len(num)):
            if i != index and num[index] == '0':
                break
            curr_str = num[index:i+1]
            curr = int(curr_str)
            length_before = len(path)
            if index == 0:
                path.append(curr_str)
                backtrack(i+1, curr, curr)
                path[length_before:] = []
            else:
                path.append('+'); path.append(curr_str)
                backtrack(i+1, evaluated + curr, curr)
                path[length_before:] = []
    backtrack(0, 0, 0)
    return res

easy

A. ["1+23", "12+3"]

B. ["123"]

C. ["1+2+3", "123"]

D. ["1+2+3"]

Solution

1. Step 1: Trace backtracking calls for num="123", target=6

   At index=0, path starts with "1". Then at index=1, add '+' and "2", evaluated=3. Then at index=2, add '+' and "3", evaluated=6, matches target, so "1+2+3" is added.

2. Step 2: Check other possible expressions

   "123" alone evaluates to 123, not 6. "1+23"=24, "12+3"=15, none equal 6. So only "1+2+3" is in result.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Only "1+2+3" sums to 6 [OK]

Hint: Only "1+2+3" equals 6 with given operators [OK]

Common Mistakes:

• Assuming "123" or "1+23" equals target

2. Consider the following BFS-based code snippet for removing invalid parentheses:

from collections import deque

def is_valid(s: str) -> bool:
    count = 0
    for c in s:
        if c == '(': count += 1
        elif c == ')':
            count -= 1
            if count < 0:
                return False
    return count == 0

def remove_invalid_parentheses_bfs(s: str):
    res = []
    visited = set([s])
    queue = deque([s])
    found = False

    while queue:
        size = len(queue)
        for _ in range(size):
            curr = queue.popleft()
            if is_valid(curr):
                res.append(curr)
                found = True
            if found:
                continue
            for i in range(len(curr)):
                if curr[i] not in ('(', ')'):
                    continue
                next_str = curr[:i] + curr[i+1:]
                if next_str not in visited:
                    visited.add(next_str)
                    queue.append(next_str)
    return res

print(remove_invalid_parentheses_bfs("()())()"))

What is the output of this code?

easy

A. ["()()()"]

B. ["()()()", "(())()"]

C. ["(())()"]

D. ["()())()"]

Solution

1. Step 1: Trace BFS levels for input "()())()"

   Initial string is invalid. BFS removes one parenthesis at each position generating candidates. The first valid strings found are "()()()" and "(())()".

2. Step 2: Confirm both valid strings are collected

   Since BFS stops adding new states after finding valid strings at current level, both minimal removal results are returned.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Both minimal valid strings are returned [OK]

Hint: BFS returns all minimal valid strings at first valid level [OK]

Common Mistakes:

• Returning only one valid string
• Returning original invalid string
• Missing one minimal valid string

3. You are given a partially filled 9x9 grid where each row, column, and 3x3 sub-box must contain digits 1 through 9 without repetition. Which algorithmic approach guarantees finding a valid solution if one exists?

easy

A. Greedy algorithm that fills cells with the first valid digit found

B. Breadth-first search exploring all possible digit placements simultaneously

C. Dynamic programming by storing subproblems of partially filled grids

D. Backtracking with constraint propagation and heuristic ordering of empty cells

Solution

1. Step 1: Understand problem constraints

   The problem requires filling cells respecting row, column, and box constraints, which is a classic constraint satisfaction problem.

2. Step 2: Identify algorithm that guarantees solution

   Backtracking with constraint propagation prunes invalid choices early, and heuristic ordering reduces branching, ensuring completeness and efficiency.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Constraint propagation + heuristic ordering is standard for Sudoku solvers [OK]

Hint: Constraint satisfaction problems need backtracking with pruning [OK]

Common Mistakes:

• Assuming greedy or BFS alone can solve Sudoku efficiently

4. What is the time complexity of the bitmask-optimized backtracking solution for the N-Queens problem, and why is the common misconception that it is O(n^3) incorrect?

medium

A. O(n^3) because there are three nested loops over rows, columns, and diagonals

B. O(2^n) because bitmasking iterates over all subsets of columns

C. O(n!) because each row places one queen and pruning reduces the search space factorially

D. O(n^2) because each queen placement checks all previous rows and columns

Solution

1. Step 1: Identify the branching factor per row

   Each row places exactly one queen, and pruning avoids invalid columns and diagonals, reducing choices drastically.

2. Step 2: Understand factorial growth

   Because queens cannot share columns, the number of ways to place queens is at most n!; pruning reduces this further but worst-case remains O(n!).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Bitmask pruning reduces search to permutations of columns [OK]

Hint: N-Queens search space is permutations, not polynomial loops [OK]

Common Mistakes:

• Assuming nested loops imply cubic time
• Confusing bitmask subsets with full subsets
• Ignoring pruning effect

5. Suppose the problem is modified so that numbers can be reused multiple times in the arrangement. Which change to the backtracking algorithm correctly adapts to this variant?

hard

A. Keep the 'used' bitmask but reset bits after each recursive call to allow reuse.

B. Remove the 'used' bitmask and allow all numbers at every position, checking divisibility only.

C. Use a frequency array to track counts of each number and decrement/increment during recursion.

D. Modify the divisibility condition to allow partial matches and keep the bitmask unchanged.

Solution

1. Step 1: Understand reuse implication

   Allowing reuse means numbers are no longer unique per position, so tracking used numbers is unnecessary.

2. Step 2: Adapt algorithm

   Removing the 'used' bitmask and checking only divisibility conditions at each position correctly counts valid arrangements with reuse.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Without uniqueness constraint, 'used' tracking is redundant [OK]

Hint: Reuse means no need to track used numbers [OK]

Common Mistakes:

• Trying to reset bitmask bits incorrectly
• Using frequency arrays unnecessarily