Which algorithm design paradigm breaks a problem into smaller subproblems, solves them independently, and combines the results?

• A. Divide and Conquer
• B. Dynamic Programming
• C. Greedy
• D. Backtracking

Answer: (A)

Dividing a problem into smaller subproblems, solving them independently, and then combining the results describes divide and conquer. In this approach, you split the original problem into similar, smaller pieces, solve each piece (usually by applying the same method recursively), and then merge those partial solutions to form the final answer. A classic example is merge sort: you split the array in half, recursively sort each half, and then merge the two sorted halves into a single sorted array.

This differs from dynamic programming, which also uses subproblems but hinges on overlapping subproblems and reusing previously computed results rather than solving independent subproblems anew. Greedy strategies focus on making locally optimal choices without necessarily decomposing the problem into independent pieces to be combined. Backtracking explores possibilities in a search tree rather than solving fixed independent subproblems and then merging their solutions.