Divide and Conquer

In divide and conquer, we divide the original problem into subproblems that have similar objectives as the original problem. We solve these subproblems recursively and combine the solution to solve the original problem. We can think of three parts for solving of the problem using divide and conquer.

Divide: Divide the problem into smaller problems that have the same objective as the original problem.

Conquer: Solve the small subproblems recursively. If they are small enough and cannot be broken further, solve them as base cases.

Combine : Combine the solutions of the subproblems to get the solution of the original problem.

Let’s consider a simple example of summing numbers. We have been given 8 numbers:

5      8      7      9      1      3      2      4 ...