# Understanding what is backtracking

in this blog post, we are going to take a look at what is backtracking and how to implement it using ruby

First thing first what is backtracking? according to Wikipedia Backtracking is a general algorithm for finding all (or some) solutions to some computational problem notably constrain satisfaction problems that incrementally builds candidates to the solutions, and abandons a candidate (“backtracks”) as soon as it determines that the candidate cannot possibly be completed to a valid solution.

To understand what backtracking is let’s take a problem and try to solve it using backtracking.

we will be given a tow input where the first number is the desired sum and the remaining is an array of numbers. Determine if the array or any of its sub-arrays can be summed to get the exact sum

analyzing the above problem here are the steps we want to follow to solve the problem

• Follow backtracking strategy and implement required base-cases to process each recursive level.
• subtract the first element of every sub-array to the sum and return true if the sum is 0 and return false if the sum is less than 0 or the array is empty.

since our steps seem complete let’s take a sample case

`def exact_sum?(sum, arr)return true if sum==0return false if sum < 0 || arr.empty?exact_sum?(sum - arr, arr[1,arr.length])endputs exact_sum?(12, [1, 2, 3, 4, 5]);# expected result => true# actual resut => false`

looking at the input you can see that if you remove 3 from the array and try to sum it you will get 12 but why do we get false? well the answer is that our above still recursive so we need to make it backtracking and the way to do that is by checking both cases where we include the first element and when we don't

By doing that here’s how the flow of our algorithm should look like

let’s include a variable K representing our sum and see how it would work

let’s implement that in our previous algorithm

`def exact_sum?(sum, arr)return true if sum==0return false if sum < 0 || arr.empty?# now we are checking both casesexact_sum?(sum - arr, arr[1,arr.length]) || exact_sum?(sum, arr[1,arr.length])endputs exact_sum?(12, [1, 2, 3, 4, 5]);# => true`

by adding a or statement the algorithm will be checking both cases and will become a backtracking algorithm but this still a little bit confusing let’s print the values of the array and the sum to fully understand the flow of our algorithm

`# the algorithm start[1, 2, 3, 4, 5]12# check for the first condition : 12-1 is not less than 0 so we subtract it from the sum[2, 3, 4, 5]11# check again 11-2 > 0 is true so we proceed[3, 4, 5]9# same thing here[4, 5]6# here 2-5 will return false so we go back to the parent call([4,5]6) and try to exclude the first case without touching the sum2# we still get false because the array will be empty and the sum will be 1 so go back to the ancestor call([3,4,5]9)and exclude the first element without touching the sum6# 9-4 > 0 is true so we proceed[4, 5]9# 5-5 is 0 so we return true5true`

And Voila!!! just with those few lines of code we have implemented a backtracking algorithm.

Thank you for reading If you have any question or suggestion contact me on Twitter

--

--