https://www.youtube.com/watch?v=DKCbsiDBN6c

In DP, we solve optimisation problem.

On the other hand, we use backtracking when we have multiple solutions and we want all the solutions.

It follows brute force approach.

We can represent the solution as a state space tree.

image.png

There is constraints. If a constraint is reached, it gets terminated with the bounding function.

Backtracking: follows DFS.

Branch and Bound: follows BFS.

Why is it called BACK-TRACKING? See here: https://www.youtube.com/watch?v=51Zy1ULau1s

https://www.youtube.com/watch?v=Zq4upTEaQyM

3 Keys:

  1. You make CHOICES from a decision space.
  2. You have CONSTRAINTS on those choices or decision space.
  3. You converges towards a GOAL recursively.

See this problem & solution with comments for understanding: Combinations

and this one as well where skipping the duplicates was challenging: