Skip to content

backtracking.md

Latest commit

 

History

History
38 lines (27 loc) · 1.86 KB

backtracking.md

File metadata and controls

38 lines (27 loc) · 1.86 KB

Backtracking

From Skeina:

At each step in the backtracking algorithm, we start from a given partial solution $a = (a_1, a_2, \dots, a_k)$ and try to extend it by adding another element at the end. After extending it, we test whether what we have so far is a complete solution. If not, the critical issue is whether the current partial solution $a$ is potentially extendible to a solution. If so, recur and continue. If not, delete the last element from $a$ and try another possibility for that position if one exists.

Pseudocode for the backtracking algorithm is as follows:

Backtrack(a, k)
	If a is a solution:
		print(a)
	Else:
		k = k + 1
		compute S_k
		while S_k != 0:
			a_k = an element in S_k
			S_k = S_k - a_k
			Backtrack(a, k)

For example, suppose we want to print all permutations of the list [1, 2, 3]. We call Backtrack([], 0). [] is not a solution, so we set k = 1. We compute S_1 = {1, 2, 3}. In the first iteration of the loop, we set a_1 = 1 and S_1 = {2, 3} and call Backtrack([1], 1). In the second iteration, we set a_1 = 2, S_1 = {1, 3} and call Backtrack([2], 1). In the last iteration, we set a_1 = 3, S_1 = {1, 2} and call Backtrack([3], 1). In general, the argument $a$ develops recursively like this image:

backtracking

The backtracking algorithm is actually DFS on a graph where each node represents a partial solution.

Related problems

Sources