Divide and Conquer

Divide and conquer solves a problem by splitting it into smaller parts, solving those parts, and combining their results.

It is a design strategy, not one specific algorithm.

Core Idea

The strategy has three steps: divide the input, conquer the smaller problems, and combine the answers. It works best when the subproblems are similar to the original problem and can be solved independently.

Merge sort is a classic example because each half can be sorted separately before the merge step combines them.

Python Example

def sum_values(values):
    if not values:
        return 0
    if len(values) == 1:
        return values[0]
 
    mid = len(values) // 2
    return sum_values(values[:mid]) + sum_values(values[mid:])

This example divides the list into halves and combines the two sums.

Common Confusions

Divide and conquer is not the same as dynamic programming. Divide and conquer usually solves independent subproblems. Dynamic programming is useful when subproblems overlap and answers should be reused.

Recursive code is not automatically divide and conquer. The problem must actually be split into smaller pieces whose results are combined.

When To Use It

Use divide and conquer when the input can be split cleanly, each part can be solved with the same idea, and the combined result is easier than solving the original directly.