Backtracking 1 - Pruning - Backtracking / Pruning

Problems
1

https://algo.monster/problems/backtracking_pruning

2

Thanks for the great lesson!

One thing, is the indentation in Template v1.1 a bit off? The last three lines are indented when it looks like they shouldn’t be.

3

thanks! yes, it’s a bit off because of the line number on the left :sweat:

4

Thanks for the lesson, can you explain why start_index is increased by variable length when pruning. does start_index not point to a level in the search space?

5

I think that this is to give the flexibility to control how you navigate the state space. In the backtracking 101 example problem, the startIndex was used as a way to track the levels of the state space tree. At the example problem, this was the length of the constructed word. The algorithm in that problem built the word one letter at a time, hence the increase of startIndex by 1. Say that the algorithm was able to add a k characters at a time, then I think we would increment the startIndex by k in this case. I hope this helps.

1 Like