When to use backtracking?

Use when you need to explore all possibilities. N-Queen, permutations, combinations, etc.

DFS visits all nodes, backtracking prunes branches when conditions not met.

Worst case O(2ⁿ) ~ O(n!). Pruning makes it much faster in practice.

Backtracking | Exhaustive Search Algorithm Complete Guide

2026년 3월 28일 · 20분 읽기 · 수정 2026년 3월 28일 Intermediate Tutorial

이 글의 핵심

Practical guide to backtracking. Complete coverage of exhaustive search algorithm with detailed examples.

Introduction

”Try All Cases, But Backtrack When Impossible”

Backtracking explores all possibilities but immediately abandons when conditions are not met.

1. Backtracking Basics

DFS vs Backtracking

DFS follows connected structures to the end while visiting, and backtracking undoes choices when they don’t satisfy conditions and tries other branches. Like erasing footsteps and returning to previous forks when reaching a dead end in a maze.

# DFS: Visit all nodes
def dfs(node):
    visit(node)
    for child in node.children:
        dfs(child)

# Backtracking: Check conditions + pruning
def backtrack(state):
    if is_solution(state):
        add_solution(state)
        return
    
    for choice in get_choices(state):
        if is_valid(choice):  # Pruning!
            make_choice(choice)
            backtrack(state)
            undo_choice(choice)  # Undo

Backtracking Template

def backtrack(state, choices):
    # 1. Base case (solution found)
    if is_complete(state):
        save_solution(state)
        return
    
    # 2. Pruning (important!)
    if not is_valid(state):
        return
    
    # 3. Try choices
    for choice in choices:
        # Make choice
        state.add(choice)
        
        # Recurse
        backtrack(state, new_choices)
        
        # Undo choice
        state.remove(choice)

2. Permutations and Combinations

Permutation

Order matters, no duplicates:

def permutations(arr, n):
    """
    Select n from arr (order matters)
    [1,2,3], n=2 → [[1,2], [1,3], [2,1], [2,3], [3,1], [3,2]]
    """
    result = []
    
    def backtrack(path, remaining):
        if len(path) == n:
            result.append(path[:])
            return
        
        for i in range(len(remaining)):
            path.append(remaining[i])
            backtrack(path, remaining[:i] + remaining[i+1:])
            path.pop()
    
    backtrack([], arr)
    return result

# Test
print(permutations([1, 2, 3], 2))
# [[1, 2], [1, 3], [2, 1], [2, 3], [3, 1], [3, 2]]

Using Visited Array:

def permutations_visited(arr, n):
    """
    Permutations using visited array (more efficient)
    """
    result = []
    visited = [False] * len(arr)
    
    def backtrack(path):
        if len(path) == n:
            result.append(path[:])
            return
        
        for i in range(len(arr)):
            if not visited[i]:
                visited[i] = True
                path.append(arr[i])
                backtrack(path)
                path.pop()
                visited[i] = False
    
    backtrack([])
    return result

Combination

Combinations ignore order and only care about what was selected. {1,2} and {2,1} are the same combination.

def combinations(arr, n):
    """
    Select n from arr (order doesn't matter)
    [1,2,3], n=2 → [[1,2], [1,3], [2,3]]
    """
    result = []
    
    def backtrack(start, path):
        if len(path) == n:
            result.append(path[:])
            return
        
        for i in range(start, len(arr)):
            path.append(arr[i])
            backtrack(i + 1, path)
            path.pop()
    
    backtrack(0, [])
    return result

# Test
print(combinations([1, 2, 3], 2))
# [[1, 2], [1, 3], [2, 3]]

Permutation vs Combination:

arr = [1, 2, 3], n=2

Permutation (order matters):
[1,2], [1,3], [2,1], [2,3], [3,1], [3,2]
Total: 6 (3P2 = 3!/(3-2)! = 6)

Combination (order doesn't matter):
[1,2], [1,3], [2,3]
Total: 3 (3C2 = 3!/(2!*1!) = 3)

3. N-Queen Problem

Problem

Place N queens on N×N chessboard (no attacks):

def solve_n_queens(n):
    """
    N-Queen problem
    """
    result = []
    board = [['.'] * n for _ in range(n)]
    
    def is_valid(row, col):
        # Check same column
        for i in range(row):
            if board[i][col] == 'Q':
                return False
        
        # Check 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 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
    
    def backtrack(row):
        if row == n:
            result.append([''.join(row) for row in board])
            return
        
        for col in range(n):
            if is_valid(row, col):
                board[row][col] = 'Q'
                backtrack(row + 1)
                board[row][col] = '.'  # Undo
    
    backtrack(0)
    return result

# Test
solutions = solve_n_queens(4)
print(f"{len(solutions)} solutions")
for sol in solutions:
    for row in sol:
        print(row)
    print()

Optimized with Sets:

def solve_n_queens_optimized(n):
    """
    N-Queen with O(1) validation using sets
    """
    result = []
    board = [['.'] * n for _ in range(n)]
    
    cols = set()
    diag1 = set()  # row - col
    diag2 = set()  # row + col
    
    def backtrack(row):
        if row == n:
            result.append([''.join(row) for row in board])
            return
        
        for col in range(n):
            if col in cols or (row - col) in diag1 or (row + col) in diag2:
                continue
            
            # Make choice
            cols.add(col)
            diag1.add(row - col)
            diag2.add(row + col)
            board[row][col] = 'Q'
            
            backtrack(row + 1)
            
            # Undo choice
            board[row][col] = '.'
            cols.remove(col)
            diag1.remove(row - col)
            diag2.remove(row + col)
    
    backtrack(0)
    return result

4. Practical Problems

Problem 1: Subset Sum

def subset_sum(arr, target):
    """
    Find subsets that sum to target
    """
    result = []
    
    def backtrack(start, path, current_sum):
        if current_sum == target:
            result.append(path[:])
            return
        
        if current_sum > target:  # Pruning
            return
        
        for i in range(start, len(arr)):
            path.append(arr[i])
            backtrack(i + 1, path, current_sum + arr[i])
            path.pop()
    
    backtrack(0, [], 0)
    return result

# Test
arr = [1, 2, 3, 4, 5]
target = 5
print(subset_sum(arr, target))
# [[1, 4], [2, 3], [5]]

Problem 2: Sudoku Solver

def solve_sudoku(board):
    """
    Solve 9x9 sudoku
    """
    def is_valid(row, col, num):
        # Check row
        if num in board[row]:
            return False
        
        # Check column
        if num in [board[i][col] for i in range(9)]:
            return False
        
        # Check 3x3 box
        box_row, box_col = 3 * (row // 3), 3 * (col // 3)
        for i in range(box_row, box_row + 3):
            for j in range(box_col, box_col + 3):
                if board[i][j] == num:
                    return False
        
        return True
    
    def backtrack():
        for i in range(9):
            for j in range(9):
                if board[i][j] == '.':
                    for num in '123456789':
                        if is_valid(i, j, num):
                            board[i][j] = num
                            
                            if backtrack():
                                return True
                            
                            board[i][j] = '.'  # Undo
                    
                    return False
        return True
    
    backtrack()
    return board

Problem 3: Generate Parentheses

def generate_parentheses(n):
    """
    Generate all valid n pairs of parentheses
    n=3 → ["((()))", "(()())", "(())()", "()(())", "()()()"]
    """
    result = []
    
    def backtrack(path, open_count, close_count):
        if len(path) == 2 * n:
            result.append(path)
            return
        
        # Add '(' if possible
        if open_count < n:
            backtrack(path + '(', open_count + 1, close_count)
        
        # Add ')' if valid
        if close_count < open_count:
            backtrack(path + ')', open_count, close_count + 1)
    
    backtrack('', 0, 0)
    return result

# Test
print(generate_parentheses(3))
# ['((()))', '(()())', '(())()', '()(())', '()()()']

5. Advanced Techniques

Pruning Strategies

# 1. Early termination
if current_sum > target:
    return  # No point continuing

# 2. Constraint propagation
if remaining_choices < needed:
    return  # Cannot complete solution

# 3. Symmetry breaking
# Skip symmetric cases to reduce search space

# 4. Memoization
memo = {}
state_key = tuple(sorted(state))
if state_key in memo:
    return memo[state_key]

Word Search

def word_search(board, word):
    """
    Find if word exists in board (can move up/down/left/right)
    """
    rows, cols = len(board), len(board[0])
    
    def backtrack(r, c, index):
        if index == len(word):
            return True
        
        if (r < 0 or r >= rows or c < 0 or c >= cols or
            board[r][c] != word[index]):
            return False
        
        # Mark as visited
        temp = board[r][c]
        board[r][c] = '#'
        
        # Try all 4 directions
        found = (backtrack(r+1, c, index+1) or
                backtrack(r-1, c, index+1) or
                backtrack(r, c+1, index+1) or
                backtrack(r, c-1, index+1))
        
        # Restore
        board[r][c] = temp
        
        return found
    
    for i in range(rows):
        for j in range(cols):
            if backtrack(i, j, 0):
                return True
    
    return False

# Test
board = [
    ['A','B','C','E'],
    ['S','F','C','S'],
    ['A','D','E','E']
]
print(word_search(board, "ABCCED"))  # True

Practical Tips

Backtracking Pattern

def backtrack(state):
    # 1. Termination condition
    if is_complete(state):
        save_solution(state)
        return
    
    # 2. Pruning (important!)
    if not is_valid(state):
        return
    
    # 3. Try choices
    for choice in get_choices():
        make_choice(choice)
        backtrack(new_state)
        undo_choice(choice)  # Undo

Optimization Tips

# ✅ Strengthen pruning
# Quickly determine impossible cases

# ✅ Optimize choice order
# Select most constrained first

# ✅ Memoization
# Prevent duplicate calculations

# ✅ State representation
# Use tuples/frozensets for hashable states

Common Mistakes

# ❌ Wrong: Forgot to undo
def backtrack(path):
    path.append(choice)
    backtrack(path)
    # Forgot path.pop()!

# ✅ Correct: Always undo
def backtrack(path):
    path.append(choice)
    backtrack(path)
    path.pop()

# ❌ Wrong: Shallow copy
result.append(path)  # path changes later!

# ✅ Correct: Deep copy
result.append(path[:])  # or list(path)

Summary

Key Points

Backtracking: Explore all cases + pruning
Pattern: Choose → Recurse → Undo
Optimization: Reduce time with pruning
Use Cases: Permutations, combinations, N-Queen, Sudoku

Problem Types

Type	Complexity	Example
Permutation	O(n!)	All arrangements
Combination	O(2ⁿ)	Subset selection
N-Queen	O(n!)	Constraint satisfaction
Sudoku	O(9^(empty cells))	Fill grid

Keywords

Backtracking, Algorithm, Exhaustive Search, Permutation, Combination, N-Queen, Sudoku, DFS, Pruning, Coding Interview, Recursion

Backtracking | Exhaustive Search Algorithm Complete Guide

이 글의 핵심

Introduction

”Try All Cases, But Backtrack When Impossible”

1. Backtracking Basics

DFS vs Backtracking

Backtracking Template

2. Permutations and Combinations

Permutation

Combination

3. N-Queen Problem

Problem

4. Practical Problems

Problem 1: Subset Sum

Problem 2: Sudoku Solver

Problem 3: Generate Parentheses

5. Advanced Techniques

Pruning Strategies

Word Search

Practical Tips

Backtracking Pattern

Optimization Tips

Common Mistakes

Summary

Key Points

Problem Types

Recommended Problems

Baekjoon

LeetCode

Programmers

Keywords

이 글의 핵심

Introduction

”Try All Cases, But Backtrack When Impossible”

1. Backtracking Basics

DFS vs Backtracking

Backtracking Template

2. Permutations and Combinations

Permutation

Combination

3. N-Queen Problem

Problem

4. Practical Problems

Problem 1: Subset Sum

Problem 2: Sudoku Solver

Problem 3: Generate Parentheses

5. Advanced Techniques

Pruning Strategies

Word Search

Practical Tips

Backtracking Pattern

Optimization Tips

Common Mistakes

Summary

Key Points

Problem Types

Recommended Problems

Baekjoon

LeetCode

Programmers

Related Posts

Keywords