Problems
What’s interesting about backtracking is that we back up only as far as needed to reach a previous decision point with an as-yet-unexplored alternative. In general, that will be at the most recent decision point. Eventually, more and more of these decision points will have been fully explored, and we will have to backtrack further and further. If we backtrack all the way to our initial state and have explored all alternatives from there, we can conclude the particular problem is unsolvable. In such a case, we will have done all the work of the exhaustive recursion and know that there is no viable solution possible. Some common problems which can be easily solved by backtracking are the N-Queens problem, graph coloring problem, knapsack problem, etc. In the N-Queens problem, we search for each possible path, if we get stuck in any path in between, we backtrack in the position from which it's called and if all cells are traveled already we can return our answer.
Min-Max Algorithm
By Firdausia Fatima
● Published At Oct 2021
In this blog, we’ll explore the famous Min-Max Algorithm.... Keep reading ..
N-Queen
By Yukti Kumari
● Published At Oct 2021
This article explains the backtracking approach to solve the N-queen problem and provides the optimized version of the backtracking method.... Keep reading ..
Generate Parentheses
By Shreya Deep
● Published At Oct 2021
In this article, we’ll learn how to generate all the combinations of well-formed parentheses.... Keep reading ..
Stone Game
By Rhythm Jain
● Published At Oct 2021
In this article, we will discuss the problem of Stone Game that covers dynamic programming, game theory, and mathematics concepts involved.... Keep reading ..
Sudoku Solver
By Aditya Narayan Joardar
● Published At Nov 2021
This is a two-part article covering the Sudoku Solver problem, asked in various competitions.... Keep reading ..
Word Break Problem using Backtracking
By Vibhor Bhatnagar
● Published At Dec 2021
This article will discuss the word break problem using backtracking ... Keep reading ..
Tug Of War
By Harsh Goyal
● Published At Dec 2021
This article will discuss the Tug of war and learn about the concept behind the approach used to solve the tug of war problem.... Keep reading ..
Permutations
By Raksha Jain
● Published At Feb 2022
The blog discusses in detail about generating all different possible permutations of numbers in a list. We’ll discuss many approaches to solve the problem and time and space complexity for each method.... Keep reading ..
Implement Hamiltonian Cycle
By Vaibhav Agarwal
● Published At Dec 2021
In this article, we will discuss the problem of printing the hamiltonian cycle for the given graph... Keep reading ..
Additive Number
By Saksham Gupta
● Published At Jan 2022
This blog will discuss how we can solve one of the most asked problems in recursion, i.e., Additive Number.... Keep reading ..
The K-th Lexicographical String of All Happy Strings of Length ‘N’
By Ishita Chawla
● Published At Dec 2021
In this blog, we will discuss the problem to find the K-th lexicographical string of all happy strings of length ‘N.’ ... Keep reading ..
Subsets
By Riya
● Published At Feb 2022
This article will discuss the “subsets problem” in which we have to generate all the subsets of a given array of unique elements and a backtracking-based method to solve the problem.... Keep reading ..
Subsets (ii)
By Riya
● Published At Feb 2022
This article will discuss the “subsets (ii) problem” in which we have to generate all the non-empty unique subsets of a given array containing duplicate elements and a BitMasking approach for solving the problem.... Keep reading ..