Dynamic Programming – Divide and Conquer method vs Backtracking

Introduction

From Merge Sort and Quick Sort, we have familiarize with Divide and Conquer concept. That is

• to break up the original input data to smaller sub data structures or problems.
• After the base problem is solved, the results are recombined.

Common implementation is to use recursive calls.

In addition, making recursive calls can also help us to traverse a decision tree, where each child node is a subproblem, and the leaf nodes provide result just like how the base problems do. The results from smaller subproblems are combined as the parent nodes (the bigger problems).

Divide and Conquer refers to the universal concept of dealing with dynamic problem, while Backtracking provides a specific code template to deal with problem where decision trees are needed.

This blog describes overall concept, and code template for Divide and Conquer technique as well revisiting the code template for Backtracking.

Concept

The following explains the concepts with the help of pseudocode templates.

Divide and Conquer

Code template

The following code template from Leetcode, could be analyzed to derive Time Complexity using Mater Theorem.

 function dac( n ):
   if n < k:  // k: some constant
     Solve "n" directly without recursion
   else:
     [1]. divide the problem "n" into "b" subproblems of equal size.
       - then the size of each subproblem would be "n/b"
     [2]. call the function "dac()" recursively "a" times on the subproblems
     [3]. combine the results from the subproblems

Time Complexity with Master Theorem

To be added

Backtracking

Backtracking is often thought as tree traversal. The following are explained from Leetcode:

• Starting from the root node, one sets out to search for solutions that are located at the leaf nodes.
• Each intermediate node represents a partial candidate solution that could potentially lead us to a final valid solution.
• At each node, we would fan out to move one step further to the final solution, i.e. we iterate the child nodes of the current node.
• Once we can determine if a certain node cannot possibly lead to a valid solution, we abandon the current node and backtrack to its parent node to explore other possibilities
  • unlike other divide and conquer problem (ig, Merge Sort), backtracking may not combine all result from child branches.

Code template:

int  recursiveCall(inputArray, stateVariable){   
    // base case:
    if (stateVariable = someValue)
         return someValue;
    int someValueOfTheLevel;
    for (int i=0; i< inputArray.max(); i++){  // to traverse horizontally between branches
         // forward logic handled here:
         int valueOfChildNode = change (inputArray, inputArray[i+1])   // call change to go deeper, to child nodes.
         // child node returns value, backtracking logic is handled here.
         valueOfChildNode = doSomething; 
    }
    // backtracking from the last branch in the child level
    // this is when the parent node gets the result from all the child node's combined logic.
    // note the values different between stateVariable is of the parent node vs the value inputArray[i+1] at line  8, which is the stateVariable of child node.
    someValueOfTheLevel = valueOfChildNode; 
    return someValueOfTheLevel;  
}

Divide and Conquer vs Backtracking

The following excerpt from Leetcode well explain the differences between 2 techniques:

1. Often the case, the divide-and-conquer problem has a sole solution, while the backtracking problem has unknown number of solutions. For example, when we apply the merge sort algorithm to sort a list, we obtain a single sorted list, while there are many solutions to place the queens for the N-queen problem.
2. Each step in the divide-and-conquer problem is indispensable to build the final solution, while many steps in backtracking problem might not be useful to build the solution, but serve as attempts to search for the potential solutions. For example, each step in the merge sort algorithm, i.e. divide, conquer and combine, are all indispensable to build the final solution, while there are many trials and errors during the process of building solutions for the N-queen problem.
3. When building the solution in the divide-and-conquer algorithm, we have a clear and predefined path, though there might be several different manners to build the path. While in the backtracking problems, one does not know in advance the exact path to the solution. For example, in the top-down merge sort algorithm, we first recursively divide the problems into two subproblems and then combine the solutions of these subproblems. The steps are clearly defined and the number of steps is fixed as well. While in the N-queen problem, if we know exactly where to place the queens, it would only take N steps to do so. When applying the backtracking algorithm to the N-queen problem, we try many candidates and many of them do not eventually lead to a solution but abandoned at the end. As a result, we do not know beforehand how many steps exactly it would take to build a valid solution. 

Using iteration instead of recursive calls

Instead of making recursive call, stack or queue could be used. This technique is also employed in Depth First Search, or Breath First Search algorithm.

The following is basic template for DFS, using stack and reiteration to traverse the decision tree.

to be added