Recursion and trees · Lesson 15 of 23
Backtracking: try and undo
One template for every "all possibilities" problem: subsets, permutations and combinations.
When a problem asks for "all ways" or "all combinations", the answer is usually backtracking: build the answer step by step, try a choice at each step, continue, then undo it and try the next. Like walking a maze: at a dead end, go back to the last junction.
function backtrack(path, choices) {
if (/* path is a complete answer */ false) { results.push([...path]); return }
for (const choice of choices) {
if (/* choice isn't allowed */ false) continue
path.push(choice) // choose
backtrack(path, choices) // explore
path.pop() // un-choose
}
}// All subsets: at each element, take it or leave it
function subsets(nums) {
const out = []
const go = (i, path) => {
if (i === nums.length) { out.push([...path]); return }
path.push(nums[i]); go(i + 1, path); path.pop() // take nums[i]
go(i + 1, path) // leave nums[i]
}
go(0, [])
return out
}
// All orderings: pick any unused element next
function permutations(nums) {
const out = [], used = new Array(nums.length).fill(false)
const go = (path) => {
if (path.length === nums.length) { out.push([...path]); return }
for (let i = 0; i < nums.length; i++) {
if (used[i]) continue
used[i] = true; path.push(nums[i])
go(path)
path.pop(); used[i] = false
}
}
go([])
return out
}
console.log(subsets([1, 2, 3]).length, permutations([1, 2, 3]).length)
console.log(permutations([1, 2, 3]).map((p) => p.join("")).join(" "))- []
- [1]
- [1, 2]
- [1, 2, 3]
- [1, 2]
- [1]
- [1, 3]
- [1]
- [1, 2]
- []
- [2]
- []
- [1]
The subsets decision tree: each level is "take or leave" one element. The leaves are the answers (2ⁿ leaves).
Spot the bug
This returns the right number of subsets, but every one comes out empty []. Which line is wrong?
Exercise
Write combine(n, k): every combination of k numbers from 1 to n (ascending within each). It must print 6 12 34.
Expected output: 6 12 34
function combine(n, k) {
}
const all = combine(4, 2)
console.log(all.length, all[0].join(""), all[all.length - 1].join(""))Practise on real problems
Practice problems that use what you learned here. Solve them in JavaScript, Python or C++.
Learn more from
Played 0 of 2 games
Sign in to save your progress and earn XP.