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.

[2026] Backtracking | Exhaustive Search Algorithm Complete Guide

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

이 글의 핵심

Master backtracking: exhaustive search algorithm complete guide. Learn backtracking basics, permutations, combinations with principles and code 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. 다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

# 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

다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다, 조건문으로 분기 처리를 수행합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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: 다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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: 다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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. 다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

# 함수 정의 및 구현
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: 아래 코드는 text를 사용한 구현 예제입니다. 코드를 직접 실행해보면서 동작을 확인해보세요.

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): 다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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: 다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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

다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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

다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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

다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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

다음은 python를 활용한 상세한 구현 코드입니다. 에러 처리를 통해 안정성을 확보합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

# 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

다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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

아래 코드는 python를 사용한 구현 예제입니다. 비동기 처리를 통해 효율적으로 작업을 수행합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

# ✅ 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

다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

# ❌ 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

[2026] Backtracking | Exhaustive Search Algorithm Complete Guide

이 글의 핵심

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

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”

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

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