Backtracking Introduction
In this page:
Backtracking Idea
Backtracking systematically explores possible choices for a problem, and the moment a choice leads somewhere that can't possibly work, it abandons that path and tries a different one instead of continuing down a dead end. It's essentially organized trial-and-error with the ability to undo a bad decision.
Example: Backtracking Idea
#include <iostream>
using namespace std;
void tryPath(int choice) {
if (choice > 3) return;
cout << "Trying choice " << choice << endl;
tryPath(choice + 1);
}
int main() {
tryPath(1);
return 0;
}public class Main {
static void tryPath(int choice) {
if (choice > 3) return;
System.out.println("Trying choice " + choice);
tryPath(choice + 1);
}
public static void main(String[] args) {
tryPath(1);
}
}def try_path(choice):
if choice > 3:
return
print("Trying choice", choice)
try_path(choice + 1)
try_path(1)#include <stdio.h>
void tryPath(int choice) {
if (choice > 3) return;
printf("Trying choice %d\n", choice);
tryPath(choice + 1);
}
int main() {
tryPath(1);
return 0;
}Login to try C/C++/Java code in the editor
State and Undo
In code, this usually means modifying some shared state to reflect a choice, recursing to explore what that choice leads to, and then reverting that same state change before trying the next choice at that level. This undo step is what makes backtracking different from plain recursive search.
Example: State and Undo
#include <iostream>
#include <vector>
using namespace std;
vector<int> path;
void explore(int n) {
if (n == 0) { for (int x : path) cout << x << " "; cout << endl; return; }
path.push_back(n);
explore(n - 1);
path.pop_back();
}
int main() {
explore(3);
return 0;
}import java.util.*;
public class Main {
static List<Integer> path = new ArrayList<>();
static void explore(int n) {
if (n == 0) { System.out.println(path); return; }
path.add(n);
explore(n - 1);
path.remove(path.size() - 1);
}
public static void main(String[] args) {
explore(3);
}
}path = []
def explore(n):
if n == 0:
print(path)
return
path.append(n)
explore(n - 1)
path.pop()
explore(3)#include <stdio.h>
int path[10], top = 0;
void explore(int n) {
if (n == 0) { for (int i = 0; i < top; i++) printf("%d ", path[i]); printf("\n"); return; }
path[top++] = n;
explore(n - 1);
top--;
}
int main() {
explore(3);
return 0;
}Login to try C/C++/Java code in the editor
Decision Tree
Every choice point branches into multiple possibilities, and following all of them forms a decision tree where each path from root to leaf represents one complete sequence of choices. Backtracking is really a depth-first walk through this tree.
Example: Decision Tree
#include <iostream>
using namespace std;
void choices(string prefix, int depth) {
if (depth == 0) { cout << prefix << endl; return; }
choices(prefix + "0", depth - 1);
choices(prefix + "1", depth - 1);
}
int main() {
choices("", 3);
return 0;
}public class Main {
static void choices(String prefix, int depth) {
if (depth == 0) { System.out.println(prefix); return; }
choices(prefix + "0", depth - 1);
choices(prefix + "1", depth - 1);
}
public static void main(String[] args) {
choices("", 3);
}
}def choices(prefix, depth):
if depth == 0:
print(prefix)
return
choices(prefix + "0", depth - 1)
choices(prefix + "1", depth - 1)
choices("", 3)#include <stdio.h>
#include <string.h>
void choices(char *prefix, int depth) {
if (depth == 0) { printf("%s\n", prefix); return; }
char next[10];
sprintf(next, "%s0", prefix); choices(next, depth - 1);
sprintf(next, "%s1", prefix); choices(next, depth - 1);
}
int main() {
choices("", 3);
return 0;
}Login to try C/C++/Java code in the editor
Pruning
Pruning means recognizing early that a partial choice can never lead to a valid solution, so you skip exploring the rest of that branch entirely rather than following it all the way to a guaranteed failure. Good pruning is often what makes an otherwise-slow backtracking solution fast enough to run.
Example: Pruning
#include <iostream>
using namespace std;
void search(int sum, int target) {
if (sum > target) return;
if (sum == target) { cout << "Found sum " << sum << endl; return; }
search(sum + 2, target);
search(sum + 3, target);
}
int main() {
search(0, 7);
return 0;
}public class Main {
static void search(int sum, int target) {
if (sum > target) return;
if (sum == target) { System.out.println("Found sum " + sum); return; }
search(sum + 2, target);
search(sum + 3, target);
}
public static void main(String[] args) {
search(0, 7);
}
}def search(total, target):
if total > target:
return
if total == target:
print("Found sum", total)
return
search(total + 2, target)
search(total + 3, target)
search(0, 7)#include <stdio.h>
void search(int sum, int target) {
if (sum > target) return;
if (sum == target) { printf("Found sum %d\n", sum); return; }
search(sum + 2, target);
search(sum + 3, target);
}
int main() {
search(0, 7);
return 0;
}Login to try C/C++/Java code in the editor
Practice
Backtracking is the standard tool for problems that ask you to generate or count all valid arrangements — combinations, permutations, board puzzles like Sudoku and N-Queens, and constraint-satisfaction problems in general.
Example: Practice
#include <iostream>
#include <vector>
using namespace std;
void combos(vector<int>& cur, int start, int n) {
cout << "{ "; for (int x : cur) cout << x << " "; cout << "}" << endl;
for (int i = start; i <= n; i++) {
cur.push_back(i);
combos(cur, i + 1, n);
cur.pop_back();
}
}
int main() {
vector<int> cur;
combos(cur, 1, 3);
return 0;
}import java.util.*;
public class Main {
static void combos(List<Integer> cur, int start, int n) {
System.out.println(cur);
for (int i = start; i <= n; i++) {
cur.add(i);
combos(cur, i + 1, n);
cur.remove(cur.size() - 1);
}
}
public static void main(String[] args) {
combos(new ArrayList<>(), 1, 3);
}
}def combos(cur, start, n):
print(cur)
for i in range(start, n + 1):
cur.append(i)
combos(cur, i + 1, n)
cur.pop()
combos([], 1, 3)#include <stdio.h>
int cur[10], top = 0;
void combos(int start, int n) {
printf("{ "); for (int i = 0; i < top; i++) printf("%d ", cur[i]); printf("}\n");
for (int i = start; i <= n; i++) {
cur[top++] = i;
combos(i + 1, n);
top--;
}
}
int main() {
combos(1, 3);
return 0;
}Login to try C/C++/Java code in the editor
Chapter Quiz — Complete all 7 topics to unlock
0/7 topics done
Complete these topics first: