Chapter 2: Recursion and Backtracking – 2. Backtracking

2.8 What is Backtracking?

Brute force approach is the approach of finding all possible solutions to find a satisfactory solution to a given problem.
Backtracking is an improvement on the brute force approach.
It systematically searches for a solution to a problem among all available options.
In backtracking we start with one possible option out of many available and try to solve the problem if we can solve the problem with the chosen move we will print the other solution otherwise we will go back and choose some other options and try to solve it.
If there are no options, we will declare that there is no solution to the problem.
Backtracking is a form of recursion.
The usual situation is that we are faced with several choices and we have to choose one of them.
After you make your choice, you’ll get a new set of options, depending on the selection you’ve made.
This process is repeated until you reach the final state.
If we make a good sequence of choices, the final state is the target state.
Backtracking can be thought of as a method of selective tree/graph traversal.
Tree is a way of representing some initial starting position (root node) and final goal state (one of the leaves).
Backtracking allows us to deal with situations where the Brute force approach will explode into too many options to consider.
At each node, we eliminate obviously impossible choices and recursively test only those that are potentially.
The nice thing about backtracking is that we only back up as needed to reach a previous decision point with an unexplored alternative.
In general, that will be the most recent decisive moment.
Eventually, more and more of this decision point will be fully explored and we will have to go back further and further.
If we go back all the way back to our original state and have explored all the alternatives from there, we can conclude that the particular problem is unsolvable.
In such a case, we would do all the work of full recursion and know that there is no possible solution .

• Sometimes the best algorithm for a problem is to try all possibilities
• This is always slow, but there are standard tools that can be used to help.
• Tools: algorithms for creating basic objects, such as binary strings (
  2 n 2^n$2^n$ possibilities for n-bit strings), permutations($n$ $!$ $n!$n ! ), combine ($n$ $!$ $/$ $r$ $!$ $($ $n$ $-$ $r$ $)$ $!$ $n!\; /r!\; (n\; –\; r)!$n ! / r ! ( n − r )! ), the general series (k – a string of length n with

  $k$ $n$ $k^n$k n possibilities), …

• Backtracking speeds up comprehensive searches by pruning.

2.9 Examples of Backtracking Algorithms?

• Binary Strings
• Generating k-ary Strings
• The Knapsack Problem
• N-Queens Problem
• Generalized Strings
• Hamiltonian Cycles (Details will be presented in chapter Graphs)
• Graph Coloring Problem

Problem-3

Generate all n-bit strings. Assume A[0..n – 1] is an array of size n.

Solution :

	public static void main(String[] args) {
		int n = 4;
		int A[] = new int[n];
		Binary(n, A);
	}
	

	public static void Binary(int n, int A[]) {
		if(n < 1) {
			System.out.println(Arrays.toString(A));
		} else {
			A[n-1] = 0;
			Binary(n-1, A);
			A[n-1] = 1;
			Binary(n-1, A);
		}
	}

And the results when I try with n = 4, you can try with different n and see the results;

Problem-4

Generate all strings of length n with elemental values ​​from

0… k − first 0 … k – 1$0\dots k-1$ .

Solution : Suppose the string we need is in the array

A [ 0.. n − first ] A[0 .. n-1]$A[\mathrm{0..}n-1]$

	public static void main(String[] args) {
		int n = 4;
		int A[] = new int[n];
		k_string(n, 3, A);
	}

	public static void k_string(int n, int k, int A[]) {
		if (n < 1) {
			System.out.println(Arrays.toString(A));
		} else {
			for (int i = 0; i < k; i++) {
				A[n-1] = i;
				k_string(n-1, k, A);
			}
		}
	}

Here is a partial result when I tried with n = 4 and k = 3.

Considering T(n) is the running time of the function k_string(n, k), we have

Using Subtraction and Conquer Master theorem we get:

BILLION ( n ) = O ( n k ) T(n) = O(n^k)$T(n)=O(n^k)$

Problem-5

Find the complexity:

BILLION ( n ) = 2 BILLION ( n – first ) + 2 n T(n) = 2T(n – 1) + 2^n$T(n)=2T(n–1)+2^{years}$

Solution :
At each level of the reconstruction tree, the number of problems is twice that of the previous level, while the amount of work done in each problem is half that of the previous level.
Formally, the i-th level has

2 i 2^i$2^i$ problems, each requires

$2$ $n$ $-$ $i$ $2\; ^\; \{\; n\; –\; i\; \}$2 n − i jobs.
Therefore, at level i exacting requirements

$2$ $n$ $2^n$2 n jobs. The depth of the tree is n => Total complexity is

O(n2n)O(n2^n)O(n2n)