Your free access ends in 7 days — and you haven’t tried it yet. Watch one algorithm run, start to finish. It takes about two minutes.

Try one problem
0
Concept

Overview

Choose → explore → un-choose
step 1 / 14
choose → explore → un-choose
[1,2]
1
[2,1]
2
[ ]
permutations found
(none yet)
The universal backtracking template
▸
1backtrack(path):
2    if path is complete: record path; return
3    for candidate in candidates(path):
4        path.push(candidate)        // choose
5        if valid(path):             // prune invalid early
6            backtrack(path)         // explore
7        path.pop()                  // un-choose
8    return
state
  • input[1, 2]

line 1Backtracking is depth-first search over a tree of partial solutions, with one extra move: UNDO. Here we build every permutation of [1, 2]. The root [ ] is the empty solution; each edge is one choice of an unused number; each leaf is a finished permutation.