Backtracking Mastery: State Space Trees, Subsets, Combinations & Permutations0%
Binary Search: Search Space Elimination, Lower Bound & Upper Bound

Backtracking Mastery: State Space Trees, Subsets, Combinations & Permutations

Beginner12 min read•Updated: Jul 11, 2026
Study MaterialsCheatsheet

Backtracking Mastery: State Space Trees, Subsets, Combinations & Permutations

Backtracking is a systematic algorithmic technique for solving constraint satisfaction and combinatorial search problems. It constructs candidate solutions incrementally and abandons (backtracks) a candidate as soon as it determines that the candidate cannot lead to a valid final solution.

1. Real-World Analogy: Navigating a Corn Maze

Imagine walking through a giant hedge or corn maze:

  1. 1
    You walk down a path until you reach a fork with 3 options: Left, Center, Right.
  2. 2
    You choose Left and walk forward.
  3. 3
    You hit a dead end (Failed Constraint).
  4. 4
    You do not stay at the dead end or teleport to the beginning; you backtrack back to the fork, undo your previous step, and try the Center path!

2. The Universal Backtracking Template

Almost every backtracking interview problem (N-Queens, Sudoku Solver, Subsets, Permutations) follows this 3-step pattern:

Output
def backtrack(candidate_path, choices):
if is_solution(candidate_path):
record_solution(candidate_path)
return
 
for choice in choices:
if is_valid(choice):
# 1. MAKE CHOICE
candidate_path.append(choice)
# 2. EXPLORE (Recurse)
backtrack(candidate_path, updated_choices)
# 3. UNDO CHOICE (Backtrack!)
candidate_path.pop()

3. Classic Problem 1: Generating All Subsets (The Power Set)

Given an integer array nums of unique elements, return all possible subsets (the power set):

Python 3 Implementation:

Python
def subsets(nums: list[int]) -> list[list[int]]:
result = []
def backtrack(start_index: int, current_subset: list[int]):
# Every state along the decision tree is a valid subset!
result.append(list(current_subset))
for i in range(start_index, len(nums)):
# 1. Make choice
current_subset.append(nums[i])
# 2. Recurse forward
backtrack(i + 1, current_subset)
# 3. Backtrack (undo choice)
current_subset.pop()
backtrack(0, [])
return result

4. Classic Problem 2: Permutations

Given an array nums of distinct integers, return all possible permutations in any order:

Modern JavaScript / TypeScript Implementation:

TypeScript
export function permute(nums: number[]): number[][] {
const result: number[][] = [];
const visited = new Set<number>();
 
function backtrack(currentPath: number[]): void {
if (currentPath.length === nums.length) {
result.push([...currentPath]); // Found full permutation
return;
}
 
for (let i = 0; i < nums.length; i++) {
if (visited.has(nums[i])) continue; // Skip already chosen elements
 
// 1. Choose
currentPath.push(nums[i]);
visited.add(nums[i]);
 
// 2. Recurse
backtrack(currentPath);
 
// 3. Backtrack
currentPath.pop();
visited.delete(nums[i]);
}
}
 
backtrack([]);
return result;
}

5. Trace Tree: Subsets of [1, 2]

Output
[] (start)
/ \
Add 1 Add 2
/ \ \
[1] [1, 2] [2]
(backtrack) (backtrack)

Output Subsets: [[], [1], [1, 2], [2]] (Total: $2^n = 2^2 = 4$ subsets).

Interactive Quiz

Multiple Choice Questions

Question 1
What does the "undo choice" (backtrack) step accomplish in a backtracking algorithm?
Question 2
How many total subsets exist for a set of $n$ distinct elements (the Power Set)?
Question 3
How many total permutations exist for an array of $n$ distinct elements?
Question 4
Why must we push a copy of the path (result.append(list(current_path)) or [...currentPath]) into the results array?
Question 5
What technique is used in backtracking to prune branches early before exploring invalid subtrees (e.g. placing two queens in the same row in N-Queens)?
Next Lesson

Binary Search: Search Space Elimination, Lower Bound & Upper Bound

Continue learning with hands-on practice, examples, and exercises in the upcoming topic.

Related Lessons

Previous LessonNext Lesson
Recursion Fundamentals: Base Cases, Recursive Leaps & Call Stack VisualsBinary Search: Search Space Elimination, Lower Bound & Upper Bound

Practice Quiz

Test your understanding of this lesson with 5 questions. Each question has one correct answer.

PreviousNext
PrevNext