Backtracking is a powerful algorithmic technique used to solve problems by exploring all possible solutions and then "backtracking" when a solution is found to be invalid or not optimal. It is often implemented using recursion.
Here are a few example questions that can be solved using backtracking along with their solutions:
N-Queens Problem: Given an integer n, place n queens on an n x n chessboard such that no two queens threaten each other.
def solveNQueens(n): result = [] board = [['.' for _ in range(n)] for _ in range(n)] backtrack(board, 0, result) return result def backtrack(board, row, result): if row == len(board): result.append([''.join(row) for row in board]) return for col in range(len(board)): if isSafe(board, row, col): board[row][col] = 'Q' backtrack(board, row + 1, result) board[row][col] = '.' def isSafe(board, row, col): n = len(board) # Check for queens in the same column for i in range(row): if board[i][col] == 'Q': return False # Check for queens in the upper left diagonal i, j = row - 1, col - 1 while i >= 0 and j >= 0: if board[i][j] == 'Q': return False i -= 1 j -= 1 # Check for queens in the upper right diagonal i, j = row - 1, col + 1 while i >= 0 and j < n: if board[i][j] == 'Q': return False i -= 1 j += 1 return True
Combination Sum: Given a set of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the numbers sum to target. Each number in candidates may be used multiple times.
def combinationSum(candidates, target): result = [] candidates.sort() backtrack(candidates, target, [], 0, result) return result def backtrack(candidates, target, current, start, result): if target == 0: result.append(current[:]) return for i in range(start, len(candidates)): if candidates[i] > target: break current.append(candidates[i]) backtrack(candidates, target - candidates[i], current, i, result) current.pop()
Generate Parentheses: Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
def generateParenthesis(n): result = [] backtrack(n, n, '', result) return result def backtrack(left, right, current, result): if left == 0 and right == 0: result.append(current) return if left > 0: backtrack(left - 1, right, current + '(', result) if right > left: backtrack(left, right - 1, current + ')', result)
These examples demonstrate how backtracking can be used to solve various problems. The backtracking algorithm explores all possible solutions and prunes branches that lead to invalid or suboptimal solutions, which can greatly improve the efficiency of solving certain problems.