Chapter 28 of 30
Backtracking & Meet-in-the-Middle
Master the backtracking template, generating combinatorial objects, pruning strategies, and meet-in-the-middle technique.
The Backtracking TemplateGenerating Combinatorial ObjectsPruningMeet-in-the-Middle
Share:
Backtracking & Meet-in-the-Middle
Backtracking explores all possibilities systematically, pruning branches that can't lead to a solution. Meet-in-the-middle splits a problem in half to reduce exponential complexity.
The Backtracking Template
hljs cpp
vector<vector<int>> results;
void backtrack(vector<int> ¤t, int start) {
if (/* is solution */) {
results.push_back(current);
return;
}
for (int i = start; i < n; i++) {
// Make choice
current.push_back(a[i]);
// Recurse
backtrack(current, i + 1); // or i for reuse
// Undo choice
current.pop_back();
}
}
Generating Combinatorial Objects
All Subsets (Power Set)
hljs cpp
vector<vector<int>> subsets;
vector<int> current;
void backtrack(int start) {
subsets.push_back(current);
for (int i = start; i < n; i++) {
current.push_back(a[i]);
backtrack(i + 1);
current.pop_back();
}
}
backtrack(0);
// 2^n subsets total
All Permutations
hljs cpp
vector<vector<int>> permutations;
vector<int> current;
vector<bool> used(n, false);
void backtrack() {
if (current.size() == n) {
permutations.push_back(current);
return;
}
for (int i = 0; i < n; i++) {
if (used[i]) continue;
used[i] = true;
current.push_back(a[i]);
backtrack();
current.pop_back();
used[i] = false;
}
}
backtrack();
// n! permutations total
All Combinations (C(n, k))
hljs cpp
vector<vector<int>> combinations;
vector<int> current;
void backtrack(int start, int k) {
if (current.size() == k) {
combinations.push_back(current);
return;
}
for (int i = start; i < n; i++) {
current.push_back(a[i]);
backtrack(i + 1, k);
current.pop_back();
}
}
backtrack(0, k);
All Subsets of Size k
Same as combinations — choose k elements from n.
Pruning
Pruning eliminates branches that can't possibly lead to a solution:
Bound Pruning
hljs cpp
void backtrack(int idx, int currentSum, int target) {
if (currentSum == target) { /* found */ return; }
if (idx == n || currentSum > target) return; // prune!
// Include a[idx]
backtrack(idx + 1, currentSum + a[idx], target);
// Exclude a[idx]
backtrack(idx + 1, currentSum, target);
}
Permutation Pruning
hljs cpp
// Skip duplicates when generating permutations
sort(a.begin(), a.end());
void backtrack() {
for (int i = 0; i < n; i++) {
if (i > 0 && a[i] == a[i - 1] && !used[i - 1]) continue; // skip duplicate
// ...
}
}
Sorting + Early Termination
hljs cpp
// Sort items; if adding the smallest remaining still exceeds target, prune
sort(a.begin(), a.end());
// In backtrack: if currentSum + (remaining items) < target, prune
Meet-in-the-Middle
Split the search space in half to reduce O(2ⁿ) to O(2^(n/2)):
Example: Count Subsets with Sum = Target
hljs cpp
// Split array into two halves
vector<int> left(a.begin(), a.begin() + n/2);
vector<int> right(a.begin() + n/2, a.end());
// Generate all subset sums for each half
vector<long long> leftSums, rightSums;
function<void(int, long long, vector<int>&, vector<long long>&)> generate =
[&](int idx, long long sum, vector<int> &arr, vector<long long> &sums) {
if (idx == arr.size()) {
sums.push_back(sum);
return;
}
generate(idx + 1, sum + arr[idx], arr, sums);
generate(idx + 1, sum, arr, sums);
};
generate(0, 0, left, leftSums);
generate(0, 0, right, rightSums);
// Sort rightSums for binary search
sort(rightSums.begin(), rightSums.end());
// Count pairs that sum to target
long long count = 0;
for (long long ls : leftSums) {
long long need = target - ls;
auto lo = lower_bound(rightSums.begin(), rightSums.end(), need);
auto hi = upper_bound(rightSums.begin(), rightSums.end(), need);
count += hi - lo;
}
Complexity
O(2^(n/2) × n/2) instead of O(2ⁿ). For n = 40, this reduces from ~10¹² to ~10⁷.
Summary
- Backtracking: make choice → recurse → undo choice
- Pruning: eliminate branches that can't lead to solutions
- Meet-in-the-middle: split in half, enumerate both halves, combine
- Use backtracking for n ≤ 20-25; meet-in-the-middle for n ≤ 40-45
- Sort input to enable duplicate skipping and early termination
Prefer reading offline? Download the full book as a PDF.
Download Free Book