AI Hints
Home›DSA in Python Tutorial›Backtracking
DSA in Python · Lesson 97 of 132

Backtracking

Try, and undo.

⏱ 2 min read▶ Video at 1:56:07🎓 Free
Watch this lesson in the DSA in Python courseWatch on YouTube ↗Full DSA in Python course

Some problems ask for every possible answer, or any answer that fits strict rules. Like solving a Sudoku. Backtracking tries a choice, explores where it leads, and if it hits a dead end, undoes the choice and tries the next one.

Backtracking
From the video: Backtracking
  • Every possible answer
  • Like solving a Sudoku
  • Try, explore, undo

Every way to arrange letters

Here we build every arrangement of A, B, and C. Path holds the letters chosen so far. At each step, we try every letter not yet used. We add it, explore further with recursion, then remove it again. That removal is the backtrack. Run it. Six arrangements, three times two times one.

permute.pypython
def arrangements(letters):
    results, path = [], []
    def explore():
        if len(path) == len(letters):
            results.append("".join(path))
            return
        for ch in letters:
            if ch not in path:
                path.append(ch)
                explore()
                path.pop()
    explore()
    return results

print(arrangements("ABC"))
Output
['ABC', 'ACB', 'BAC', 'BCA', 'CAB', 'CBA']

The backtracking template

Every backtracking solution has the same skeleton. If the current path is complete, record it. Otherwise, for each possible choice, make the choice, recurse, and then undo it. Because it explores everything, it's usually exponential, like O of N factorial. So it's only practical for small inputs, or with clever pruning.

keyvalue
Complete?record the answer
Chooseadd to the path
Explorerecurse
Undoremove from the path

Summary

Backtracking makes a choice, explores it, and undoes it, to try every possibility. Next, generating subsets.

Key takeaways
  • Choose
  • Explore
  • Undo
Next up: Subsets — every combination