Related Tags

python
communitycreator

# What is backtracking in Python?

shreshta

### 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:

1. N-queens problem
2. Graph coloring
3. Crosswords
4. 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 res
else:
return [
y + x
for 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

python
communitycreator

CONTRIBUTOR

shreshta
RELATED COURSES

View all Courses

Keep Exploring

Learn in-demand tech skills in half the time