What is backtracking in Python?
What is backtracking?
Backtracking includes deciding on the simplest choice out of many possibilities. We first select a choice and back down from it if we attain a kingdom in which that particular choice no longer provides the desired solution.
We repeat that procedure and go through all of the available options until we find the preferred solution.
Algorithms that use backtracking
Some algorithms that use backtracking include:
- N-queens problem
- Graph coloring
- Crosswords
- Rat in the maze
Recursion vs. backtracking
Recursion involves a function calling itself until it reaches the base case.
Backtracking uses recursion to discover all of the possibilities until we get the best end result for the problem.
Code
The code below is an example of finding all of the possible arrangements of a given set of letters.
def permutation(list, res):if list == 1:return reselse:return [y + xfor y in permutation(1, res)for x in permutation(list - 1, res)]print(permutation(1, ["a","b","c"]))print(permutation(2, ["a","b","c"]))
Explanation
When we select a pair, we use backtracking to see if that particular pair was previously created. The pair is added to the answer list if it hasn’t already been formed; otherwise, it is ignored.
RELATED TAGS
CONTRIBUTOR
