Backtracking | 1

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 Video.  Code.  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. InterviewBit.  GFG. 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