educative.io

May Provide example with each condition

Courses
, ,
#1

By just mentioning valid or invalid points never clear the concept. It needs examples with each point. So that we can fit the rule with the example.

#2

Thanks for your feedback Imran – I think you make a fair point. Given the level of abstraction at which we are discussing the applicability of the backtracking technique, I see that it would probably help to mention a concrete example or two along with each of the criteria in the section “Does my problem fit this pattern?”

#3

Yes, because the person who wrote these points has something in his mind or has got experience from certain questions. But here only mentioning points make the reader directionless. Like where these points may fit and may not.
From my understanding

  1. While constructing any single candidate solution, all paths must be explored:
    Problem: Generating all possible subsets of a set of elements.
  2. The problem requires us to consider all feasible solutions in order to select the best one:
    Problem: Traveling Salesman Problem (TSP).
  3. The problem requires us to compile a list of all feasible solutions:
    Problem: Finding all valid parentheses combinations.

Problems where better not to use Backtracking

  1. Not sure
    Problem : ???
  2. It is sufficient to construct just one feasible solution to solve the problem.
    Problem: Find path from Source to Destination, only single solution, so instead of Backtracking we may use DFS
#4

Thanks Imran. That’s about right, and it is, in fact, a good suggestion that we’ll also try to incorporate in this section in the other pattern introduction lessons in the course.

1 Like