Backtracking

Question 1

What is a general formula for backtracking?

Answer 1

It will be recursive in nature.

You will iterate through the input and then at each loop, have a recursive call, followed by an alteration to the input (pop an element out, call on the next element in the array).

Question 2

What are some good indicators you might need to use backtracking?

Answer 2

You are given small input size (< 20 ) and/or are asked to provide all possible combinations.

Question 3

What is backtracking and why is it used?

Answer 3

Backtracking is an optimization on top of a brute force solution.

You take the generic ‘check all possible solutions’ and then impose a constraint on it, removing a lot of options and saving you time.