Backtracking problems Pattern and Approach. Leetcode
All problems in this page are important and have been asked across various companies – Amazon, Microsoft, Ola, Flipkart ….
- 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
- The Knight’s tour problem. Generate all the path for a Knight’s Movement. GFG Code
- The N Queens Placement Video, TR Video. GFG
- [Pending] Generate All Palindromic Decompositions Of A String. Video GFG Code
- Generate All Permutations Of A String. Video Code GFG
- Compute All Mnemonics For A Phone Number (Recursion/Backtracking Problem). Video. GFG BFS Recursive Solution
- Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses of length 2*n. Video. Code. GFG
- Implement A Sudoku Solver Video GFG SWE – Code
- Generate n-bit Gray Codes. Backtracking. Non Backtracking.
- 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
- Boggle. Video
- [Subset] Generate The Power Set Of An Array – Backtracking/Recursion (“Subsets” on LeetCode). Video GFG- Recursive Bit-GFG. InterviewBit . **Code (Decision Tree)
- [Pending] [Combinations] [Pending] Generate All Subsets Of Size K – Generate A Restricted Powerset (“Combinations” on Leetcode). Video. InterviewBit
- [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
- [Subset II] Given a collection of integers that might contain duplicates, S, return all possible subsets. InterviewBit . Code
- [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
- 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
- [Skip] Partition To K Equal Sum Subsets From An Array of Integers – The Backtracking Approach. Video
- [Skip] The IP Address Decomposition Problem – Compute All Valid IP Addresses From Raw IP String. Video
- 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.- We start from the source cell and calls BFS procedure.
- We maintain a queue to store the coordinates of the matrix and initialize it with the source cell.
- We also maintain a Boolean array visited of same size as our input matrix and initialize all its elements to false.
- We LOOP till queue is not empty
- Dequeue front cell from the queue
- Return if the destination coordinates have reached.
- 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};
- [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
[…] (Blog, […]
LikeLike