Backtracking Interview Questions and Answers

Backtracking is a systematic way of trying out different sequences of decisions until we find one that "works." Backtracking does not generate all possible solutions first and checks later. It tries to generate a solution and as soon as even one constraint fails, the solution is rejected and the next solution is tried. Backtracking can be understood as as searching os a tree for a particular "goal" leaf node. Backtracking in that case is a depth-first search with any bounding function. All solution using backtracking is needed to satisfy a complex set of constraints.

Recursion describes the calling of the same function that you are in. The typical example of a recursive function is the factorial. You always need a condition that makes recursion stop (base case). Backtracking is when the algorithm makes an opportunistic decision*, which may come up to be wrong. If the decision was wrong then the backtracking algorithm restores the state before the decision. It builds candidates for the solution and abandons those which cannot fulfill the conditions. A typical example for a task to solve would be the Eight Queens Puzzle. Backtracking is also commonly used within Neuronal Networks. Many times backtracking is not implemented recursively. If backtracking uses recursion its called Recursive Backtracking P.S. * Opportunistic decision making refers to a process where a person or group assesses alternative actions made possible by the favorable convergence of immediate circumstances recognized without reference to any general plan.

Exhaustive Search is an algorithmic technique in which first all possible solutions are generated first and then we select the most feasible solution by applying some rules. Since it follows the most naive approach, it is a.k.a Brute-Force Search. This approach is one of the most expensive algorithmic techniques, mainly in terms of time complexity. It is also, therefore, one of the most naive ones.

1. Using Backtracking you built a solution (that is a structure where every variable is assigned a value).
2. It is however possible that during construction, you realize that the solution is not successful (does not satisfy certain constraints), then you backtrack: you undo certain assignments of values to variables in order to reassign them. Like when looking for a book because at first you check drawers in the first room, but it's not found, so youbacktrack out of the first room to check the drawers in the next room. It's also called Trial & Error.

Backtracking is an algorithmic paradigm aimed at improving the time complexity of the exhaustive search technique if possible. Backtracking does not generate all possible solutions first and checks later. It tries to generate a solution and as soon as even one constraint fails, the solution is rejected and the next solution is tried. Instead of exhaustive search the backtracking algorithm tries to construct a solution incrementally, one small piece at a time. It's a systematic way of trying out different sequences of decisions until we find one that works.

A permutation, also called an “arrangement number” or “order,” is a rearrangement of the elements of an ordered list S into a one-to-one correspondence with S itself (or in simple english: permutation is each of several possible ways in which a set or number of things can be ordered or arranged). A string of length n has n! permutation: ABC

// original string (3)

ABC ACB BAC BCA CBA CAB

// permutations 3! = 6

To print all permutations of a string use backtracking implemented via recursion: Try each of the letters in turn as the first letter and then find all the permutations of the remaining letters using a recursive call. The base case is when the input is an empty string the only permutation is the empty string. In other words, you simply traverse the tree, and when you reach the leaf you print the permutation. Then you backtrack one level up, and try another option. Moving one level up the tree is what we call the backtracking in this case.

Complexity Analysis: Time Complexity: O(n!) Space Complexity: O(n!) For any given string of length n there are n! possible permutations, and we need to print all of them so Time complexity is O(n * n!) . The function will be called recursively and will be stored in call stack for all n! permutations, so Space complexity is O(n!) . Implementation: JS

// using backtracking
let permute = (str, left = 0, right = str.length - 1) => {
  //If left index is equal to right index
  //Print the string permutation
  if(left == right){
    console.log(str);
  }else{
    for(let i = left; i <= right; i++){
      //Swap the letters of the string
      str = swap(str, left, i);
      //Generate the permutation with swapped letters
      permute(str, left+1, right);
      //Restore the letters back to their position, e.q. backtrack to prev state of the string
      str = swap(str, left, i);
    }
}
}//Function to swap the letters of the string
let swap = (str, left, right) => {
  let arr = str.split('');
  [arr[left], arr[right]] = [arr[right], arr[left]];
  return arr.join('');
}
Java
public static void permutation(String str) {
  permutation("", str);
}
private static void permutation(String prefix, String str) {
  int n = str.length();
  if (n == 0) System.out.println(prefix);
  else {
    for (int i = 0; i < n; i++)
    // take new prefix from string[i], put it as a first element and construct the rest of the

    string
    permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i+1, n));
  }
}
PY
# using backtracking
def permute(a, l, r):
if l==r:
print toString(a)
else:
for i in xrange(l,r+1):
a[l], a[i] = a[i], a[l]
permute(a, l+1, r)
a[l], a[i] = a[i], a[l]
# backtrack
# Driver program to test the above function
string = "ABC"
n = len(string)
a = list(string)
permute(a, 0, n-1)

Depth First Traversal or Depth First Search is a edge based recursive algorithm for traversing (visiting) all the vertices of a graph or tree data structure using a stack. The purpose of the algorithm is to mark each vertex as visited while avoiding cycles. DFS traverse/visit each vertex exactly once and each edge is inspected exactly twice. DFS is a genuinely recursive algorithm that uses stack for backtracking purposes, not for storing the vertex discovery "front" (as is the case in BFS). The DFS algorithm works as follows: Start by putting any one of the graph's vertices on top of a stack. Take the top item of the stack and add it to the visited list. Create a list of that vertex's adjacent nodes. Add the ones which aren't in the visited list to the top of the stack. Keep repeating steps 2 and 3 until the stack is empty. DFS example step-by-step: Considering A as the starting vertex which is explored and stored in the stack. B successor vertex of A is stored in the stack. Vertex B have two successors E and F, among them alphabetically E is explored first and stored in the stack. The successor of vertex E, i.e., G is stored in the stack. Vertex G have two connected vertices, and both are already visited, so G is popped out from the stack. Similarly, E s also removed. Now, vertex B is at the top of the stack, its another node(vertex) F is explored and stored in the stack. Vertex F has two successor C and D, between them C is traversed first and stored in the stack. Vertex C only have one predecessor which is already visited, so it is removed from the stack. Now vertex D connected to F is visited and stored in the stack.

As vertex D doesn’t have any unvisited nodes, therefore D is removed. Similarly, F, B and A are also popped. The generated output is – A, B, E, G, F, C, D.

Explicit constraints are rules that restrict each

elements (nodes) of

solution space only from a given,

predefined set (described by some
Explicit rules)

Implicit constraints describe the way in which the

elements (nodes) of
solution space must relate (depend)

to each other.