**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.Code**InterviewBit .**

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