💡 The recursion explores new branches starting with queen at (0,1).
reconstruct
End of Search, Return Total Solutions
All recursive calls complete, returning the total count of 2 valid solutions for the 4-queens problem.
💡 The final count aggregates all valid leaf nodes found during recursion.
Line:return backtrack(0, 0, 0, 0)
💡 The algorithm efficiently counted all solutions without enumerating invalid boards.
class Solution:
def totalNQueens(self, n: int) -> int:
def backtrack(row, cols, pos_diags, neg_diags):
# STEP 1: Check if all rows are placed
if row == n:
return 1
count = 0
# STEP 2: Calculate available positions
available_positions = ((1 << n) - 1) & ~(cols | pos_diags | neg_diags)
while available_positions:
# STEP 3: Extract rightmost available position
position = available_positions & -available_positions
# STEP 4: Remove chosen position
available_positions &= available_positions - 1
# STEP 5: Recurse with updated bitmasks
count += backtrack(row + 1,
cols | position,
(pos_diags | position) << 1,
(neg_diags | position) >> 1)
return count
return backtrack(0, 0, 0, 0)
📊
N-Queens II (Count Solutions) - Watch the Algorithm Execute, Step by Step
Watching the algorithm step through each recursive call and bitmask update reveals how pruning and bit operations efficiently solve the problem without brute force.
✓ Bitmasking efficiently encodes and updates constraints for columns and diagonals, enabling fast pruning.
This insight is hard to see from code alone because bit operations are compact and abstract, but visualization shows how constraints evolve.
✓ The recursion tree structure clearly shows how the algorithm explores each row's queen placements and backtracks when no options remain.
Seeing the tree helps understand the exhaustive search and pruning, which is less obvious from reading code.
✓ Each leaf node corresponds to a complete valid solution, and the algorithm counts these leaves to find the total number of solutions.
Understanding that counting solutions is about counting leaf nodes clarifies the base case and return values.
Practice
(1/5)
1. Consider the following code snippet for counting beautiful arrangements. What is the final output when n = 2?
easy
A. 1
B. 3
C. 2
D. 4
Solution
Step 1: Trace backtrack calls for n=2
Positions: 1 and 2. At pos=1, try nums 1 and 2. Both satisfy divisibility. For pos=2, remaining number also satisfies divisibility.
Step 2: Count valid permutations
Permutations: [1,2] and [2,1] both valid, total count = 2.
Final Answer:
Option C -> Option C
Quick Check:
Both permutations satisfy conditions, so output is 2 [OK]
Hint: Check all permutations for small n manually [OK]
Common Mistakes:
Off-by-one in position indexing
Counting invalid permutations
2. Given the following Python code for generating parentheses, what is the content of result after calling generateParenthesis(2)?
easy
A. ['((', '))']
B. ['()()', '(())']
C. ['(())', '()()']
D. ['()()', '(()']
Solution
Step 1: Trace backtrack calls for n=2
Sequences generated are '(())' and '()()' in that order due to DFS with backtracking.
Step 2: Confirm order and validity
Both sequences are valid balanced parentheses of length 4, matching expected output.
Final Answer:
Option C -> Option C
Quick Check:
Output matches known valid sequences for n=2 [OK]
Hint: Backtracking generates sequences in DFS order [OK]
Common Mistakes:
Confusing order of sequences
Including invalid partial sequences
3. What is the time complexity of the optimal backtracking solution that generates all valid parentheses sequences for input n?
medium
A. O(2^{2n} * n) because it generates all sequences and checks validity
B. O(n^2) because it builds sequences of length 2n with nested loops
C. O(n!) because it permutes parentheses positions
D. O(\frac{4^n}{n^{3/2}}) because the number of valid sequences is the nth Catalan number
Solution
Step 1: Identify number of valid sequences
The number of valid parentheses sequences is the nth Catalan number, approximately 4^n / (n^{3/2}).
Step 2: Analyze backtracking time
Backtracking generates all valid sequences, so time is proportional to number of sequences times sequence length, which is O(4^n / n^{3/2} * n) = O(4^n / n^{1/2}).
Final Answer:
Option D -> Option D
Quick Check:
Matches known Catalan number growth for valid parentheses [OK]
Hint: Catalan number growth dominates complexity [OK]
Common Mistakes:
Confusing brute force with backtracking complexity
Assuming factorial complexity
4. The following code attempts to generate all permutations of a list using Heap's algorithm but contains a subtle bug:
def permute(nums):
res = [nums[:]]
c = [0] * len(nums)
i = 0
while i < len(nums):
if c[i] < i:
if i % 2 == 0:
nums[0], nums[i] = nums[i], nums[0]
else:
nums[c[i]], nums[i] = nums[i], nums[c[i]]
res.append(nums)
c[i] += 1
i = 0
else:
c[i] = 0
i += 1
return res
What is the bug in this code?
medium
A. The used array c is not reset properly, causing infinite loop
B. Appending nums directly without copying causes all entries in res to reference the same list
C. Swapping nums[0] and nums[i] when i is even is incorrect logic
D. The initial res list should be empty, not contain nums[:] at start
Solution
Step 1: Identify how results are stored
The code appends nums directly to res without copying.
Step 2: Understand consequences of appending references
Since nums is mutated in-place, all entries in res point to the same list, resulting in duplicates of the final permutation.
Final Answer:
Option B -> Option B
Quick Check:
Appending a copy nums[:] fixes the bug [OK]
Hint: Always append a copy of mutable lists to results [OK]
Common Mistakes:
Forgetting to copy before appending results in duplicate references
5. Consider the following buggy code snippet for restoring IP addresses. Which line contains the subtle bug that causes invalid IP addresses to be included?
def restore_ip_addresses(s: str) -> List[str]:
res = []
stack = [(0, [])]
while stack:
start, path = stack.pop()
if len(path) == 4:
if start == len(s):
res.append(".".join(path))
continue
remaining_segments = 4 - len(path)
remaining_chars = len(s) - start
if remaining_chars < remaining_segments or remaining_chars > 3 * remaining_segments:
continue
for length in range(1, 4):
if start + length > len(s):
break
segment = s[start:start+length]
# Bug: Missing check for leading zeros
if length == 3 and int(segment) > 255:
continue
stack.append((start + length, path + [segment]))
return res
medium
A. Line missing check for segments with leading zeros
B. Line checking if segment length is 3 and value > 255
C. Line pruning based on remaining characters and segments
D. Line appending new segment to stack
Solution
Step 1: Identify missing validation
The code lacks a check to reject segments with leading zeros like '00' or '01', which are invalid.
Step 2: Confirm other checks are correct
Check for segment > 255 and pruning are present and correct; appending to stack is correct.
Final Answer:
Option A -> Option A
Quick Check:
Missing leading zero check allows invalid IP segments [OK]
Hint: Leading zero check is mandatory to avoid invalid IPs [OK]