Backtracking

When studying algorithms related to solving computing problems, it is important to look into the Backtracking algorithm. The Backtracking algorithm essentially refers to searching and going through every possible combination in order to solve a particular computing problem. Broadly classifying, the backtracking algorithm can be divided into 3 further categories. These include searching for all feasible solutions, searching for the best solution, and searching for any feasible solution. In this category, we will look into every dimension of the backtracking algorithm in great detail.

Introduction

Backtracking is basically an improvement of the brute force approach. It checks all the possible ways. In backtracking, we search with one possible or let's say starting option from many possible options and try to solve the problem. If we get stuck in between or do not get the required answer, then we will backtrack or revert back from the point we started and we will look for some other paths possible. After going through all the possible options, if no answer is received, then we can conclude that no such path or answer is possible for the given problem.

Backtracking and Recursion

By Vibhor Bhatnagar

● Published At Dec 2021

In this article, we will discuss two important concepts of the world of programming: backtracking and recursion.
... Keep reading ..

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

## Top Problems related to Backtracking

Minimum Cost to Destination

Find Number Of Islands

Shortest Path in a Binary Matrix

Sudoku Solver

Print Permutations - String

Valid Sudoku

Word Break-1

Rat In a Maze All Paths

N Queens

Partial BST

Palindrome Partitioning

Convert Bst To The Greater Sum Tree

Maze with N doors and 1 Key

Partition to K equal sum subsets

Word Search - l

Permutations

K - Sum Path In A Binary Tree

Possible Balanced Strings

Print All Paths

The N - Queens Puzzle

Paths in a Maze