Backtracking

DSA · Algorithm Techniques

Theory

Backtracking builds candidate solutions one choice at a time and abandons ("backtracks" from) a partial candidate as soon as it cannot lead to a valid solution. The template is choose, explore, un-choose. It explores a search tree of possibilities, so the worst case is exponential, but pruning invalid branches early makes it practical for puzzles and combinatorial problems.

Why we use it

It systematically finds all solutions (or one valid solution) to constraint problems without writing complex special cases.

When to use it

Use it for permutations, combinations, subsets, N-Queens, Sudoku, word search, and generating valid parentheses.

How it works

  1. choose(state)
  2. State is a complete solution? Yes: Record it. No: For each option.
  3. Option is valid? Yes: Apply it, recurse, then undo it. No: Try next option.
  4. Explored all options

Syntax

def backtrack(path, choices):
    if complete(path): record(path); return
    for c in choices:
        if valid(c):
            path.append(c)        # choose
            backtrack(path, ...)  # explore
            path.pop()            # un-choose

Example

def subsets(items):
    result = []
    def bt(i, path):
        if i == len(items):
            result.append(list(path)); return
        bt(i + 1, path)
        path.append(items[i]); bt(i + 1, path); path.pop()
    bt(0, [])
    return result

def solve_queens(n):
    solutions = []
    cols, d1, d2 = set(), set(), set()
    board = []
    def place(r):
        if r == n:
            solutions.append(list(board)); return
        for c in range(n):
            if c in cols or r - c in d1 or r + c in d2:
                continue
            cols.add(c); d1.add(r - c); d2.add(r + c); board.append(c)
            place(r + 1)
            cols.remove(c); d1.remove(r - c); d2.remove(r + c); board.pop()
    place(0)
    return solutions

print("Subsets of [1,2,3]:", subsets([1, 2, 3]))
sols = solve_queens(6)
print("6-Queens solutions:", len(sols), "| first:", sols[0])

Key points

DSA topics

Introduction to DSA

Arrays and Searching

Sorting Algorithms

Linked Lists

Stacks and Queues

Hashing

Trees

Heaps

Graphs

Algorithm Techniques

Classic Algorithms

Dynamic Programming

T
Tech Town
Log InSign Up Free
Home SQL Python DSA Power BI Snowflake Databricks Spark Gen AI Practice Problems Contest Blog

Data Structures & Algorithms

The complete DSA roadmap: theory, why and when to use every structure and algorithm, Big O complexity, and Python code you can run right here in the browser.

{{ sectionCount }}
Sections
{{ topicCount }}
Topics
Free
Forever
Hands-on practice Practice DSA Online 251 problems across 13 patterns, with hidden tests and step-by-step optimal solutions. Start practising →
Section {{ sec.num }}

{{ sec.label }}

DSA  /  {{ current.sectionLabel }}  /  {{ current.name }}

{{ current.name }}

Theory

{{ current.def }}

Why we use it

{{ current.why }}

When to use it

{{ current.when }}

Flowchart — how {{ current.name }} works
{{ nd.text }}
{{ nd.text }}
◇ {{ nd.text }}
Yes → {{ nd.yes }}
No → {{ nd.no }}
Step-by-step visualisation
{{ cell.v }}
{{ cell.i }} {{ cell.tag }}
Step {{ vizStepLabel }}: {{ vizNote }}
■ comparing ■ swapping / moving ■ done / found ■ out of range
Complexity & Pseudocode
{{ current.syntax }}
Example Code
{{ current.example }}
▶ Try It Live — runs real Python 3 in your browser (first run loads the engine)
{{ liveOutput }}
{{ liveError }}
Key Points — click to check off as you learn
  • {{ pt.mark }} {{ pt.text }}

Share this topic