#Divide and conquer meaning code

#Divide and conquer meaning code

The provided code can be said it backtracks when a solution path fails. Which seems general enough to fit all DP problems under it. Erickson defines the 'recursive strategy' as:Ī backtracking algorithm tries to construct a solution to a computational problem incrementally, one small piece at a time. So in this case, according to the recursion tree, are not always independent (they overlap).

Divide the given instance of the problem into several independent smaller instances of exactly the same problem.

In Erickson's Algorithms (section 1.6), it says:

In Skiena's ADM (Section 5.3.1), it says:Ī typical divide-and-conquer algorithm breaks a given problem into a smaller pieces, each of which is of size n/b.īy this interpretation is doesn't meet the as we divide our solution by coins and each coin amount being a different size. If indeed it has backtracking and D&C algorithms then recursion would be the best answer as it contains both. Recursion being the most general and encapsulating of backtracking, D&C, and DP. I think the options here are recursion, backtracking, divide-and-conquer, and dynamic programming. My best interpretation is that its backtracking. The most practical answer is it doesn't matter. Exhaustive search algorithms are ones that work by trying all possible options and returning the best, and I think that’s the best way of classifying your strategy. The algorithm you’ve proposed essentially works by enumerating all possible ways of making change, then returning the one that uses the fewest coins. I would classify your algorithm as belonging to a different family of exhaustive search.

But my colleagues sometimes describe what you’re doing as backtracking!) (When I teach intro programming, I usually classify algorithms this way. Your algorithm doesn’t have this property, since it explores all options and then takes the best. Similarly, backtracking algorithms usually, but not always, work by committing to a decision, recursively searching to see whether a solution exists given that decision, then unwinding the choice if it turns out not to lead to a solution. (Then again, not all divide-and-conquer algorithms have this property.

(See, for example, mergesort, quicksort, binary search, closest pair of points, etc.) In that sense, your algorithm doesn’t nicely map onto the divide-and-conquer paradigm, since the subproblems you’re considering involve some degree of overlap in the subproblems they solve. I know both are implemented via Recursion, but I would like to know which paradigm my Brute Force solution belongs to: Divide and Conquer or Backtracking.Ī complication in categorizing your algorithm is that there aren’t clear, well-defined boundaries between different classes of algorithms and different people might have slightly different definitions in mind.įor example, generally speaking, divide-and-conquer algorithms involve breaking the problem apart into non-overlapping subproblems. I can also say it is Backtracking: we are enumerating all combinations of coin frequencies which satisfy the constraints. I can say it is Divide and Conquer: We are dividing the problem into smaller sub-problems, solving individually and using those individual results to construct the result for the original problem. The Recursion Tree looks like: Recursion Tree I know it is best solved by using Dynamic Programming, but I want to focus on my Brute Force solution: class Solution:ĭef coinChange(self, coins: List, amount: int) -> int:Ĭurr_min = min(curr_min, helper(amount-coin) + 1) Let’s use as an example the problem LeetCode 322.