Algorithms and Data Structure : part 3 Back tracking

Back Tracking  and  DFS






Back Tracking is travelling a path in a matrix/graph/tree using DFS and checking if this is required solution.


If not, we can PRUNE that path and use DFS on other path.


DFS uses STACK.




As I am solving some questions, the best way to apply back track is think


1) Can you have the problem statement expressed in terms of matrix.
2) IF yes, you will be apply to easily visualize how you can apply back tracking .


Since in matrix , you will be apply to move in 4 directions at max, so at each node you can save node data of possible movements in STACK. Once you see your solution is not met, with the direction you are moving, you will start popping the elements.


This is basic skeleton of back tracking , but you will have to add conditions of movement depending on question and solution you want.


For ex : Suppose given a  Set of   6 elements { 1,2,3,4,5,6}  you have to find all possible permutation of  3 element subset.


Ways to solve problem.
1) generate all subsets and select only those whose size is 3 : Brute Force
2) Second Use 3 for loops and select different elements in each loop : Iterative solution
3) Rather than for loops , use recursion : Recursive solution
4) Think all 6 number as graph nodes, interconnected to each other, so in you matrix you can move in any direction for a given node. Now apply DFS+BackTracking , as soon you have 3 elements in your stack, you will stop that route. Then you will pop out one element and move to next element.


Now  for this particular problem, recursive will give the simplest code. 


So many a times you have to see , which approach will work out the best.




Suppose in some other example you have a matrix with 0 and 1.  In that case you have to move from 0,0 position to 7,7 position and you can move only where 0 are present.  And now you have to find the route.


In that case back tracking will give simplest code. ( NOTE SIMPLEST Doesn't MEANS FASTEST, but since those problems when we visualize , we can easily map them to back tracking, so you can make the code easily)




Some problems you can work on


1)  Given {1,2,3,4,5,6,7,8,9,10}  find all subsets whose sum is 10.
        try  back tracking and some other approach, and see advantages of one over other.


2) Take a matrix composed of  0 and 1 , with 0 as path and have multiple paths from topmost-left corner to bottommost-right corner , now PRINT all the possible paths.