Backtracking
Definition
Backtracking is a refined “Brute Force” technique. It builds a solution step-by-step. If it realizes the current path cannot lead to a valid solution, it stops immediately, backtracks (goes back to the previous step), and tries a different option. 
How it Works
- Choose: Pick an option.
- Constraint Check: Is this option valid?
- Explore: If valid, move to the next step recursively.
- Un-choose: If you hit a dead end, undo the choice (backtrack) and try the next option.
Real-World Analogy
Walking through a Maze: You walk down a path. You hit a dead end. You don’t just stand there; you turn around, walk back to the last intersection, and try the other path.
Example
Problem: Generating all permutations of “ABC”.
- Start with A. Next can be B. Next C. (ABC) -> Valid.
- Backtrack to B. Try to put A? Already used.
- Backtrack to start. Try B first…
Code Example
PythonJavaCC++
# Generate all permutations using Backtracking
def permute(nums):
result = []
def backtrack(path, remaining):
# Base case: no numbers left
if not remaining:
result.append(path)
return
for i in range(len(remaining)):
# Choose one number and explore
backtrack(
path + [remaining[i]],
remaining[:i] + remaining[i+1:]
)
backtrack([], nums)
return result
print(permute([1, 2, 3]))
import java.util.*;
public class Permutations {
static List<List<Integer>> result = new ArrayList<>();
static void backtrack(List<Integer> path,
List<Integer> remaining) {
if (remaining.isEmpty()) {
result.add(new ArrayList<>(path));
return;
}
for (int i = 0; i < remaining.size(); i++) {
List<Integer> newPath = new ArrayList<>(path);
newPath.add(remaining.get(i));
List<Integer> newRemaining =
new ArrayList<>(remaining);
newRemaining.remove(i);
backtrack(newPath, newRemaining);
}
}
public static void main(String[] args) {
List<Integer> nums = Arrays.asList(1,2,3);
backtrack(new ArrayList<>(), nums);
System.out.println(result);
}
}
#include <stdio.h>
void swap(int* a, int* b) {
int temp = *a;
*a = *b;
*b = temp;
}
void permute(int arr[], int l, int r) {
if (l == r) {
for (int i = 0; i <= r; i++)
printf("%d ", arr[i]);
printf("\n");
return;
}
for (int i = l; i <= r; i++) {
swap(&arr[l], &arr[i]);
permute(arr, l + 1, r);
swap(&arr[l], &arr[i]); // backtrack
}
}
int main() {
int arr[] = {1,2,3};
permute(arr, 0, 2);
return 0;
}
#include <iostream>
#include <vector>
using namespace std;
void permute(vector<int>& nums, int l) {
if (l == nums.size()) {
for (int n : nums)
cout << n << " ";
cout << endl;
return;
}
for (int i = l; i < nums.size(); i++) {
swap(nums[l], nums[i]);
permute(nums, l + 1);
swap(nums[l], nums[i]); // backtrack
}
}
int main() {
vector<int> nums = {1,2,3};
permute(nums, 0);
return 0;
}
Complexity Analysis
- Time Complexity: Generally Exponential, e.g., O(N!) for permutations or O(2^N) for subsets.
- Space Complexity: O(N) for the recursion stack.
Use Cases
- Puzzles: Sudoku solvers, N-Queens problem, Crosswords.
- Combinatorics: Generating all passwords, subsets, or arrangements.