backtracking - OpenGenus IQ: Learn Computer Science

Knight’s Tour Problem

The Knight's Tour Problem is one of the famous problem in which we have the knight on a chessboard. The knight is supposed to visit every square exactly once. We have explored Backtracking and Warnsdorff's algorithm.

Algorithms

8 Queens Problem using Backtracking

In this article, we will solve the 8 queens problem using backtracking which will take O(N!) time complexity. We demonstrate it with code.

Algorithms

Subset Sum Problem solved using Backtracking approach 【O(2^N) time complexity】

In this article, we will solve Subset Sum problem using a backtracking approach which will take O(2^N) time complexity

Algorithms

All Valid Word Breaks of a Sentence 【O(2^N) time complexity】

We are given with a valid sentence without any spaces and we are given with a dictionary of words. We need to print all the possible ways to break the sentence so that all the breaked words belongs to the dictionary.

Algorithms

Using Bron Kerbosch algorithm to find maximal cliques in O(3^(N/3))

Bron–Kerbosch algorithm is an enumeration algorithm for finding maximal cliques in an undirected graph. Any n-vertex graph has at most 3^n⁄3 maximal cliques, and the worst-case running time of the Bron–Kerbosch algorithm (with a pivot strategy) is O(3^n⁄3).