# Backtracking | 1

Backtracking problems Pattern and Approach. Leetcode

All problems in this page are important and have been asked across various companies – Amazon, Microsoft, Ola, Flipkart ….

1. Rat in a Maze -> Generate all the path from source to destination in a maze.
Problem Statement and approach video, Solution – Video
Generate one of the path from source to destination in a maze –
Print one of the possible path – GFG Code

2. The Knight’s tour problem. Generate all the path for a Knight’s Movement. GFG Code

3. The N Queens Placement  Video, TR Video.  GFG

4. [Pending] Generate All Palindromic Decompositions Of A String. Video GFG  Code

5. Generate All Permutations Of A String. Video Code GFG

6. Compute All Mnemonics For A Phone Number (Recursion/Backtracking Problem). Video.  GFG   BFS    Recursive Solution

7. Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses of length 2*n. Video. Code. GFG

8. Implement A Sudoku Solver  Video   GFG  SWE – Code

9. Generate n-bit Gray Codes. Backtracking. Non Backtracking.

10. String Permutation Algorithm -> in lexicographically sorted order and handles duplicate. TR VideoCode.  InterviewBit
complexity – O(n!)
O(n!) unique strings if no repeated character.
Lexicographically n-th permutation of a string. GFG.  InterviewBit

11. Boggle. Video

12. [Subset] Generate The Power Set Of An Array – Backtracking/Recursion (“Subsets” on LeetCode). Video  GFG- Recursive    Bit-GFG.    InterviewBit . **Code   (Decision Tree)

13. [Pending] [Combinations] [Pending] Generate All Subsets Of Size K – Generate A Restricted Powerset (“Combinations” on Leetcode). Video. InterviewBit

14. [Combination Sum] Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
Code. InterviewBit Video Code

15. [Subset II] Given a collection of integers that might contain duplicates, S, return all possible subsets. InterviewBit . Code

16. [Combination Sum II] Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T. InterviewBit Code

17. Given an array of positive integers arr[] and a sum x, find all unique combinations in arr[] where the sum is equal to x. InterviewBitGFG. Code

18. [Skip] Partition To K Equal Sum Subsets From An Array of Integers – The Backtracking Approach. Video

19. [Skip] The IP Address Decomposition Problem – Compute All Valid IP Addresses From Raw IP String. Video

20. Shortest Path in a Binary Maze. This is solved using Lee Algorithm which is a basic BFS. GFG Link
Algo: The idea is inspired from Lee algorithm and uses BFS.

1. We start from the source cell and calls BFS procedure.
2. We maintain a queue to store the coordinates of the matrix and initialize it with the source cell.
3. We also maintain a Boolean array visited of same size as our input matrix and initialize all its elements to false.
1. We LOOP till queue is not empty
2. Dequeue front cell from the queue
3. Return if the destination coordinates have reached.
4. For each of its four adjacent cells, if the value is 1 and they are not visited yet, we enqueue it in the queue and also mark them as visited.

If we are at a cell and want to generate the cells around it (not the diagonal one, only those on left, right, up, down) check the code how to efficiently do that.
int rowNum[] = {-1, 0, 0, 1};
int colNum[]   = {0, -1, 1, 0};

21. [DP] Count the number of path in a maze. GFG
Algo:  We build upon the logic to find the path from in a maze. We we the same logic to navigate the maze. When we reach the destination generally we end the program. But here we will keep a counter when we reach the final dest. Then we return false and start backtracking to find an alternate path. This way all the paths will be discovered. Code

## One thought on “Backtracking | 1”

1. […] (Blog, […]

Like