Divide and Conquer Algorithms with Source Code

Divide and conquer is an algorithm design paradigm based on multi-branched recursion.

A divide and conquer algorithm works by recursively breaking down a problem into two or more sub-problems of the same type, until these become simple enough to be solved directly. The solutions to the sub-problems are then combined to give a solution to the original problem.

Recursive Fibonacci:

Divide and Conquer Strategy

1. Divide input into partitions of almost equal size
2. Recursively solve the subproblems dened by the partition
3. Combine the solutions to the subproblems into a single answer and pass it back as the answer to the recursion call

It must be possible to perform steps 1,3 eficiently for the D+C approach to work well. Subproblems must be independent for step 2 to be possible. Adding up the entries in an array satisfies these conditions.

Divide and Conquer Algorithms with Source Code

See the below source code of Divide and conquer algorithm problem. Hope you will understand it.

Read more : 0/1 Knapsack Using Dynamic Programming Approach with Source Code

Hope it can help you.