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

이 글의 핵심

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.

# 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

자주 묻는 질문 (FAQ)

Q. 이 내용을 실무에서 언제 쓰나요?

A. Master backtracking: exhaustive search algorithm complete guide. Learn backtracking basics, permutations, combinations w… 실무에서는 위 본문의 예제와 선택 가이드를 참고해 적용하면 됩니다.

Q. 선행으로 읽으면 좋은 글은?

A. 각 글 하단의 이전 글 또는 관련 글 링크를 따라가면 순서대로 배울 수 있습니다. C++ 시리즈 목차에서 전체 흐름을 확인할 수 있습니다.

Q. 더 깊이 공부하려면?

A. cppreference와 해당 라이브러리 공식 문서를 참고하세요. 글 말미의 참고 자료 링크도 활용하면 좋습니다.

같이 보면 좋은 글 (내부 링크)

이 주제와 연결되는 다른 글입니다.

BFS와 DFS | 그래프 탐색 알고리즘 완벽 정리
동적 프로그래밍(DP) | 코딩 테스트 필수 알고리즘 완벽 정리
[Graph Data Structure | Adjacency List· Matrix](/en/blog/algorithm-series-05-graph/

이 글에서 다루는 키워드 (관련 검색어)

Algorithm, Backtracking, DFS, Coding Interview, Permutation, Combination 등으로 검색하시면 이 글이 도움이 됩니다.

이 글이 도움이 되셨나요?

여러분의 피드백은 더 나은 콘텐츠를 만드는 데 도움이 됩니다

문제가 있거나 개선 제안이 있으시면 연락처로 알려주세요.

Keyboard Shortcuts

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

자주 묻는 질문 (FAQ)

Q. 이 내용을 실무에서 언제 쓰나요?

Q. 선행으로 읽으면 좋은 글은?

Q. 더 깊이 공부하려면?

같이 보면 좋은 글 (내부 링크)

이 글에서 다루는 키워드 (관련 검색어)

이 글이 도움이 되셨나요?

Keyboard Shortcuts

이 글의 핵심

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

자주 묻는 질문 (FAQ)

Q. 이 내용을 실무에서 언제 쓰나요?

Q. 선행으로 읽으면 좋은 글은?

Q. 더 깊이 공부하려면?

같이 보면 좋은 글 (내부 링크)

이 글에서 다루는 키워드 (관련 검색어)

이 글이 도움이 되셨나요?