N-Queens II (Count Solutions)

📋

Problem

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.

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

Edge cases: n = 1 → 1 solutionn = 2 → 0 solutions (no valid placements)n = 3 → 0 solutions (no valid placements)

</>

IDE

def totalNQueens(n: int) -> int:public int totalNQueens(int n)int totalNQueens(int n)function totalNQueens(n)

def totalNQueens(n: int) -> int:
    # Write your solution here
    pass

class Solution {
    public int totalNQueens(int n) {
        // Write your solution here
        return 0;
    }
}

#include <vector>
using namespace std;

int totalNQueens(int n) {
    // Write your solution here
    return 0;
}

function totalNQueens(n) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: 0Returning zero for all inputs due to missing base case or incorrect recursion termination.✅ Add base case: if row == n, return 1 to count a valid solution.

Wrong: Incorrect positive count for n=2 or n=3Conflict checks missing or incorrect, allowing invalid queen placements.✅ Check columns and both diagonals for conflicts before placing a queen.

Wrong: Less than correct count for n=6 or n=7Greedy or partial backtracking skipping valid solutions.✅ Implement full backtracking exploring all columns per row without early pruning except conflicts.

Wrong: Timeout on n=14Naive recursion with board validation causing exponential blowup.✅ Use bitmask optimization to track columns and diagonals efficiently and prune early.

✓

Test Cases

Focus on handling smallest boards and no-solution cases correctly.

Watch out for common algorithmic traps like greedy placement and off-by-one errors.

Optimize your solution with bitmasking and pruning to handle large n efficiently.

t1_01basic

Input4

Expected2

⏱ Performance - must finish in 2000ms

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

💡 Try placing queens row by row and check conflicts.

💡 Use backtracking to explore all valid placements.

💡 Count solutions when all rows are successfully assigned.

Why it failed: Incorrect count for n=4 indicates backtracking or conflict check is flawed. Fix by ensuring diagonal and column conflicts are correctly detected.

✓ Correctly counts all valid 4-queen placements.

t1_02basic

Input5

Expected10

⏱ Performance - must finish in 2000ms

There are 10 distinct ways to place 5 queens on a 5x5 board with no conflicts.

💡 Backtracking explores all column choices per row.

💡 Check columns and diagonals for conflicts before placing.

💡 Count solutions only when all rows are assigned.

Why it failed: Incorrect count for n=5 means conflict detection or recursion termination is wrong. Fix by verifying all conflict checks and base case return.

✓ Correctly counts all valid 5-queen placements.

t2_01edge

Input1

Expected1

⏱ Performance - must finish in 2000ms

Only one queen on 1x1 board, trivially one solution.

💡 Check base case when n=1.

💡 No conflicts possible with single queen.

💡 Return 1 immediately or after placing queen.

Why it failed: Fails n=1 test if base case not handled or recursion never returns 1. Fix by adding base case for row == n returning 1.

✓ Correctly handles smallest board with one queen.

t2_02edge

Input2

Expected0

⏱ Performance - must finish in 2000ms

No valid placements for 2 queens on 2x2 board without conflicts.

💡 Try all placements and verify no solutions found.

💡 Check that conflict detection prevents invalid placements.

💡 Return 0 if no full assignments possible.

Why it failed: Fails n=2 test if code returns nonzero solutions. Fix by ensuring conflict checks correctly reject all invalid placements.

✓ Correctly returns zero for no solution cases.

t2_03edge

Input3

Expected0

⏱ Performance - must finish in 2000ms

No valid placements for 3 queens on 3x3 board without conflicts.

💡 Try all column placements per row and check conflicts.

💡 No full assignment possible for n=3.

💡 Return 0 if no valid solutions found.

Why it failed: Fails n=3 test if code returns nonzero solutions. Fix by verifying conflict checks and backtracking logic.

✓ Correctly returns zero for no solution cases.

t3_01corner

Input6

Expected4

⏱ Performance - must finish in 2000ms

There are 4 distinct solutions for 6-queens problem.

💡 Avoid greedy placement; try all columns per row.

💡 Check all diagonals and columns for conflicts.

💡 Count solutions only when all rows assigned.

Why it failed: Greedy approach fails here by missing solutions. Fix by implementing full backtracking instead of greedy column choice.

✓ Correctly counts all solutions avoiding greedy traps.

t3_02corner

Input7

Expected40

⏱ Performance - must finish in 2000ms

There are 40 distinct solutions for 7-queens problem.

💡 Ensure no reuse of columns or diagonals across rows.

💡 Use sets or bitmasks to track conflicts efficiently.

💡 Count solutions only when all rows assigned.

Why it failed: Confusing 0/1 vs unbounded placement leads to counting invalid solutions multiple times. Fix by ensuring each row places exactly one queen.

✓ Correctly enforces one queen per row and counts solutions.

t3_03corner

Input8

Expected92

⏱ Performance - must finish in 2000ms

There are 92 distinct solutions for 8-queens problem.

💡 Check off-by-one errors in recursion termination.

💡 Verify conflict checks include both diagonals and columns.

💡 Count solutions only when row == n.

Why it failed: Off-by-one error in recursion causes missing or extra counts. Fix by ensuring base case triggers exactly when row == n.

✓ Correctly counts all solutions with proper recursion base case.

t4_01performance

Input14

Expectednull

⏱ Performance - must finish in 2000ms

n=14, backtracking with pruning or bitmask optimization must complete within 2 seconds.

💡 Use bitmask to track columns and diagonals efficiently.

💡 Prune invalid branches early in recursion.

💡 Avoid naive board validation to meet time constraints.

Why it failed: TLE occurs if brute force or naive conflict checks used. Fix by implementing bitmask-based pruning and efficient backtracking.

✓ Algorithm runs within time limit using bitmask optimization.

Practice

1. You need to generate all combinations of balanced parentheses pairs for a given number n. Which algorithmic approach guarantees generating only valid sequences without generating invalid ones first?

easy

A. Brute force: generate all possible sequences of '(' and ')' of length 2n, then filter valid ones

B. Backtracking with pruning: build sequences by adding '(' or ')' only when it keeps the sequence valid

C. Greedy approach: always add '(' until n is reached, then add ')' to close all opened parentheses

D. Dynamic programming: count the number of valid sequences using Catalan number formula

Solution

1. Step 1: Understand problem constraints

   We want to generate all valid parentheses sequences without generating invalid ones first.

2. Step 2: Analyze approaches

   Brute force generates all sequences including invalid ones, greedy fails to generate all valid sequences, DP counts sequences but does not generate them. Backtracking with pruning adds '(' or ')' only when valid, thus generating only valid sequences.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Backtracking with pruning avoids invalid sequences [OK]

Hint: Backtracking prunes invalid sequences early [OK]

Common Mistakes:

• Thinking greedy can generate all valid sequences
• Confusing counting with generating sequences

2. What is the time complexity of the optimal factorial-based algorithm to find the k-th permutation of n numbers, and why?

medium

A. O(n^2) because each of the n iterations involves removing an element from a list of size up to n.

B. O(n!) because it generates all permutations internally.

C. O(n log n) due to sorting operations inside the algorithm.

D. O(n) because factorial computations and indexing are constant time per iteration.

Solution

1. Step 1: Analyze the main loop

   The algorithm runs a loop n times to select each digit of the permutation.

2. Step 2: Consider list removal cost

   Removing an element from the numbers list is O(n) in worst case, so total is O(n * n) = O(n^2).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Each iteration's pop is linear, leading to quadratic time [OK]

Hint: List pop at arbitrary index costs O(n), not O(1) [OK]

Common Mistakes:

• Assuming factorial computations dominate time
• Thinking it's O(n) due to fixed loop count
• Confusing factorial precomputation with sorting

3. What is the time complexity of the optimal iterative backtracking solution with pruning for restoring IP addresses from a string of length n, and why?

medium

A. O(3^4) because each of the 4 segments can be length 1 to 3, and pruning limits exploration

B. O(4^n) because each character can start a new segment or continue the previous one

C. O(n^4) because we try all partitions of the string into 4 segments

D. O(n!) due to permutations of segment lengths

Solution

1. Step 1: Identify branching factor per segment

   Each segment can be length 1, 2, or 3, so branching factor is at most 3 per segment.

2. Step 2: Calculate total combinations

   There are 4 segments, so total combinations are at most 3^4 = 81. Pruning further reduces this.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Time complexity depends on fixed 4 segments with max 3 choices each [OK]

Hint: Fixed 4 segments with max 3 lengths each -> 3^4 complexity [OK]

Common Mistakes:

• Assuming complexity depends on n^4
• Confusing permutations with combinations

4. What is the time complexity of the optimal backtracking solution for the Word Search problem, where N is the number of cells in the board and L is the length of the word?

medium

A. O(N * 4^L) because each cell explores 4 directions for each character

B. O(N * 3^L) because after the first character, each step explores up to 3 directions

C. O(N * L) because each cell is visited once per character

D. O(N^2) because the board is searched multiple times for each character

Solution

1. Step 1: Identify branching factor per recursion

   From each cell, first character has 4 directions, subsequent steps have at most 3 (excluding the cell we came from).

2. Step 2: Calculate total complexity

   For each of N cells, explore up to 3^L paths, so total time is O(N * 3^L).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   3^L accounts for pruning revisits, not 4^L [OK]

Hint: Remember first step has 4 directions, next steps 3 due to no revisiting [OK]

Common Mistakes:

• Assuming 4^L for all steps
• Confusing L with N in complexity

5. Suppose the problem is modified so that IP address segments can be reused multiple times (i.e., segments can overlap and be repeated). Which modification to the backtracking algorithm correctly handles this variant without generating duplicates or invalid IPs?

hard

A. Remove the pruning condition on remaining characters and segments to allow overlapping segments

B. Use a memoization cache keyed by (start, segments formed) to avoid recomputing paths

C. Allow segments to be reused by resetting start index to previous segment start after each addition

D. Change the algorithm to generate all permutations of segments without pruning

Solution

1. Step 1: Understand reuse implies overlapping segments

   Allowing reuse means the same substring can be used multiple times, potentially causing repeated computations.

2. Step 2: Apply memoization to avoid duplicates

   Memoization keyed by (start, segments formed) prevents recomputing the same subproblems and avoids duplicates.

3. Step 3: Evaluate other options

   Removing pruning causes inefficiency; resetting start index breaks segment order; generating all permutations ignores validity and pruning.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Memoization efficiently handles reuse without duplicates [OK]

Hint: Memoization avoids recomputation when segments can be reused [OK]

Common Mistakes:

• Removing pruning causes timeouts
• Resetting start index breaks segment order