Backtracking
GOALTry every possibility, and step back out of the wrong ones.
Like finding your way through a maze: take a path, and if it dead-ends, come back and try another. In code — make a choice, recurse, then UNDO the choice on the way back. That last step is the one people forget.
ON THIS PAGE
//THE EXAMPLE
#include <iostream>
#include <vector>
using namespace std;
void permute(vector<int>& v, vector<bool>& used, vector<int>& cur) {
if (cur.size() == v.size()) {
for (int x : cur) cout << x;
cout << " ";
return;
}
for (int i = 0; i < (int)v.size(); i++) {
if (used[i]) continue;
used[i] = true;
cur.push_back(v[i]);
permute(v, used, cur);
cur.pop_back();
used[i] = false;
}
}
int main() {
vector<int> v = {1, 2, 3};
vector<bool> used(3, false);
vector<int> cur;
permute(v, used, cur);
cout << endl;
return 0;
}123 132 213 231 312 321
//LINE BY LINE
Watch it run
It starts with an empty list. Three choices are open.
The shape every backtracking solution has
The problems differ but the skeleton does not. Learn it once and a new problem is only a matter of filling in the parts.
void solve(State& s) {
if (isComplete(s)) { record(s); return; }
for (each choice) {
if (!allowed(choice, s)) continue;
apply(choice, s); // 1. choose
solve(s); // 2. go deeper
undo(choice, s); // 3. undo <- the step people forget
}
}The allowed test is where the speed comes from. Cutting a doomed branch EARLY removes exponentially much work — that is called pruning.
Counting them, or listing them
If the problem asks "how many ways", you do not need to keep the answers — a counter is enough, and it saves all that memory.
int count = 0;
void solve(State& s) {
if (isComplete(s)) { count++; return; } // just count it
...
}If you do have to list them, store a COPY. Push the working array itself and later steps change it — every saved answer ends up identical.