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

Leave a Reply

Please log in using one of these methods to post your comment: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s