InterviewBit Academy is now Scaler!
InterviewBit Academy is now Scaler Academy!

Level 5

Backtracking

Backtracking is the method of building the solution one piece at a time recursively and incrementally. The method keeps removing all those bits that do not contribute to the solution.

One such real-life example is a maze. At every dead end, you trace back your steps and set out for another path- thus setting a perfect example for backtracking. Similarly, Sudoku works on the same principle.

That’s what backtracking is, retracing back the steps and discarding the choice that doesn't add on to build the correct solution.

Backtracking

Important Tutorials

1. Recursion Basics Using Factorial
View Tutorial
2. Complexity Analysis Of Recursive Programs
View Tutorial
3. Why Recursion Is Not Always Good
View Tutorial
4. Time Complexity Analysis Of Recursion
View Tutorial
5. Space Complexity Analysis Of Recursion
View Tutorial
6. Backtracking
View Tutorial
7. Backtracking Pseudocode
View Tutorial

Backtracking Problems

Subsets
Problem Score Companies Time Status
Subset 250 60:24
Combinations 300 44:05
Combination Sum 300 59:05
Combination Sum II 300 39:16
Subsets II 300 38:14
Bruteforce builder
Problem Score Companies Time Status
Letter Phone 250 51:36
Palindrome Partitioning 300 64:14
Generate all Parentheses II 350
50:22
Pruned builder
Problem Score Companies Time Status
Palindrome Partitioning 300 64:14
Generate all Parentheses II 350
50:22
NQueens 550 70:07
Sudoku 700 62:33
Permutations
Problem Score Companies Time Status
Permutations 350 38:21
Maths and backtracking
Problem Score Companies Time Status
Gray Code 350
54:48
Kth Permutation Sequence 350 67:45
Game solving
Problem Score Companies Time Status
NQueens 550 70:07
Sudoku 700 62:33