# Factorial
def factorial(n):
if n <= 1: # Base case
return 1
return n * factorial(n - 1) # Recursive case
# Power
def power(base, exp):
if exp == 0:
return 1
return base * power(base, exp - 1)
# Sum of digits
def sum_digits(n):
if n == 0:
return 0
return n % 10 + sum_digits(n // 10)
print(sum_digits(12345)) # 15# Fibonacci — O(2^n) due to redundant calls
def fib(n):
if n <= 1:
return n
return fib(n-1) + fib(n-2)
# Tree for fib(5):
# fib(5)
# / \
# fib(4) fib(3)
# / \ / \
# fib(3) fib(2) fib(2) fib(1)
# / \ / \ / \
# fib(2) fib(1) ... ...def backtrack(choices, state, results):
if is_complete(state):
results.append(copy(state))
return
for choice in choices:
if is_valid(choice, state):
make_choice(state, choice)
backtrack(choices, state, results)
undo_choice(state, choice) # BACKTRACK!def subsets(nums):
result = []
def backtrack(start, current):
result.append(list(current))
for i in range(start, len(nums)):
current.append(nums[i])
backtrack(i + 1, current)
current.pop() # Backtrack
backtrack(0, [])
return result
print(subsets([1, 2, 3]))
# [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]def permutations(nums):
result = []
def backtrack(current, remaining):
if not remaining:
result.append(list(current))
return
for i in range(len(remaining)):
current.append(remaining[i])
backtrack(current, remaining[:i] + remaining[i+1:])
current.pop() # Backtrack
backtrack([], nums)
return result
print(permutations([1, 2, 3]))
# 6 permutationsdef solve_n_queens(n):
result = []
board = ['.'] * n
def is_safe(row, col, queens):
for r, c in queens:
if c == col or abs(r - row) == abs(c - col):
return False
return True
def place_queen(row, queens):
if row == n:
result.append([''.join(board[:c] + ['Q'] + board[c+1:])
for c in queens] if queens else [])
return
for col in range(n):
if is_safe(row, col, queens):
place_queen(row + 1, queens + [(row, col)])
place_queen(0, [])
return result
solutions = solve_n_queens(4)
print(f'4-Queens: {len(solutions)} solutions')
for sol in solutions:
for row in sol:
print(f' {row}')
print()def solve_sudoku(board):
def find_empty():
for i in range(9):
for j in range(9):
if board[i][j] == 0:
return (i, j)
return None
def is_valid(num, row, col):
if num in board[row]: return False
if num in [board[r][col] for r in range(9)]: return False
box_r, box_c = 3 * (row // 3), 3 * (col // 3)
for r in range(box_r, box_r + 3):
for c in range(box_c, box_c + 3):
if board[r][c] == num: return False
return True
empty = find_empty()
if not empty: return True
row, col = empty
for num in range(1, 10):
if is_valid(num, row, col):
board[row][col] = num
if solve_sudoku(board):
return True
board[row][col] = 0 # Backtrack!
return FalseImplement: 1) `factorial(n)` recursive. 2) `subsets(nums)` returning all subsets. 3) `permutations(nums)` returning all permutations. 4) `solve_n_queens(n)` returning board configurations. 5) `combination_sum(candidates, target)` finding all unique combinations that sum to target (candidates can be reused). Demonstrate all with small inputs and print results clearly.