Backtracking Patterns — DSA Pattern

The Backtracking Patterns pattern applies when you need subsets, permutations, combinations, N-Queens, and word search. Its time complexity is O(2ⁿ) or O(n!) depending on the branching and space complexity O(n) recursion depth. It is used in 19 problems on Thita, including Check if Word Can Be Placed In Crossword, Combinations and Combination Sum. Common variations are N-Queens / Constraint Satisfaction and Parentheses Generation.

Master backtracking algorithms including subsets, permutations, combinations, N-Queens, and word search. Exhaustive search with pruning for constraint satisfaction.

Backtracking Patterns is pattern 11 of 16 in the Thita.ai DSA course. It covers subsets, permutations, combinations, N-Queens, and word search, split into 7 subpatterns and about 3 hours of study. It is one of the interview-critical patterns, so it is worth covering before your first onsite.

Subpatterns of Backtracking Patterns

Each subpattern below has its own theory page and problem set. They are listed in the order the course teaches them.

• Subsets (Include/Exclude) — Generate all subsets using include/exclude decision pattern. Handle duplicates in subsets. (core technique)
• Permutations — Generate all permutations using backtracking. Handle duplicates and next permutation. (core technique)
• Combination Sum — Find combinations that sum to target using backtracking. Handle reuse and duplicates. (core technique)
• Word Search / Path Finding in Grid — Search for words in grid using backtracking. Handle visited cells and path restoration. (core technique)
• N-Queens / Constraint Satisfaction — Solve N-Queens and Sudoku using backtracking with constraint propagation. (important variation)
• Parentheses Generation — Generate all valid parentheses combinations using backtracking with balance tracking. (important variation)
• Palindrome Partitioning — Partition string into palindromic substrings using backtracking. (depth topic)

How to practise Backtracking Patterns on Thita.ai

Read the theory for a subpattern, then solve its problems in the browser editor. Your solution runs against the problem's test cases, and the AI coach gives a hint on the technique you are missing rather than the finished answer. Progress is tracked per subpattern, so the tracker shows which of the 7 Backtracking Patterns subpatterns you have covered. Topics covered here include backtracking, backtracking algorithm, subsets generation, permutations, combinations, N-Queens, word search, constraint satisfaction.

Related DSA patterns

• Heap (Priority Queue) Patterns — Top K elements, K-way merge, two heaps for median, and scheduling.
• Greedy Patterns — Interval scheduling, jump games, stock trading, and task scheduling.
• Dynamic Programming (DP) Patterns — Fibonacci, Kadane, knapsack, LCS, LIS, edit distance, grid paths, and word break.
• Graph Traversal Patterns (DFS & BFS) — DFS/BFS traversal, topological sort, shortest paths, Union-Find, and MST.
• Bit Manipulation Patterns — XOR tricks, counting bits, power-of-two checks, and Hamming weight.
• All 16 DSA patterns
• The DSA patterns sheet
• Coding practice