Backtracking

Question 1

Generate Parentheses (Medium)

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

Answer 1

class PString { open; closed; string }
Put 0, 0, ‘’ onto queue
BFS
If open and closed = n, add to results
If open < n, inc open, update string and add to queue
If closed < open, inc closed, update string and add to queue

Time & Space - O(4^n / sqrt(n)) - nth catalan number

Question 2

Sudoku Solver (Hard)

Write a program to solve a Sudoku puzzle by filling the empty cells.

Answer 2

solve(board, 0, 0)
double for loop from row to 9 and col to 9
reset col to 0 after each row iteration
If not empty space, continue
If empty, iterate through 1 to 9 and check validity
If valid, set board[i][j] to c and solve(board, i, j + 1)
If solve returns true, also return true
Otherwise reset board[i][j] to empty
If iterate through all chars with no solves, return false
If iterate through entire board, return true

To check validity, iterate from 1 to 9 and check same row, same column for matching number
Then check surrounding square for matching number
rowStart = floor(x / 3) * 3
colStart = floor(y / 3) * 3
double for loop 0 < 3
check board[rowStart + i][colStart + j] for c

Time - O(9!)^9
Space - 81 square grid

Question 3

N-Queens (Hard)

Given an integer n, return all distinct solutions to the n-queens puzzle.

Answer 3

Array to track results and columns (columns[row] = col of queen for that row)
placeQueens(0, n, columns, results)
if (row === n) push to results
else loop through columns, check for queen validity
If valid, columns[row] = col, placeQueens(row + 1, n, columns, results)

To check validity
Iterate from row 0 to current row, check for same column
col2 = columns[row2]
check for diagonal - colDistance = Math.abs(col2 - col1), rowDistance = row1 - row2
if colDistance == rowDistance then on same diagonal

Time - O(N!)
Space - O(N)

Question 4

Expression Add Operators (Hard)

Given a string that contains only digits 0-9 and a target value, return all possibilities to add binary operators (not unary) +, -, or * between the digits so they evaluate to the target value.

Answer 4

recurse(0, 0, 0, 0, [], nums, ans, target)
index, prevOperand, currOperand, value, ops

if index === nums.length and value = target and current = 0, push ops.slice(1).join() to ans, return
calc curr = curr * 10 + parseInt(nums[index])

if (curr > 0) no-op recursion… recurse(index + 1, ….)
addition recursion
ops.push(‘+’); ops.push(curr.toString()); recurse(index + 1, curr, 0, val + curr, …)
ops.pop() ops.pop()

if (ops.length) (so not first number)
subtraction recursion
ops.push(‘-‘); ops.push(curr.toString()); recurse(index + 1, -curr, 0, val - curr, …)
ops.pop() ops.pop()

multiplication recursion

ops. push(‘*’) ops.push(curr.toString()) recurse(index + 1, prev * curr, 0, val - prev + (curr * prev), …)
ops. pop() ops.pop()

Time - O(4^n)
Space - O(n)

Question 5

Remove Invalid Parentheses (Hard)

Remove the minimum number of invalid parentheses in order to make the input string valid. Return all possible results.

Answer 5

create set to track valid expressions
track minRemovedCount = initialize to Infinity
recurse(s, 0, 0, 0, [], 0)
s, index, leftCount, rightCount, expression, removedCount
if index = s.length and leftCount = rightCount and removedCount <= minRemovedCount, add expression to set
update minRemovedCount if necessary (Math.min() and clear set)
else
grab current char
if char is not ( or ), push char to expression and recurse(index + 1), expression.pop()
else
recurse for deletion recurse(s, index + 1, …. removedCount + 1)
push current char to expression
if current char is (, recurse(s, index + 1, leftCount + 1, …)
else if rightCount < leftCount (pruning), recurse(s, index + 1, leftCount, rightCount + 1, …)
expression.pop()

Time - O(2 ^ N)
Space - O(N)