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
- Implement the recursive function to find all the possible sub-arrays recursively.
- 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==0
return false if sum < 0 || arr.empty?
exact_sum?(sum - arr[0], arr[1,arr.length])
end
puts exact_sum?(12, [1, 2, 3, 4, 5]);
# expected result => true
# actual resut => falselooking 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==0
return false if sum < 0 || arr.empty?
# now we are checking both cases
exact_sum?(sum - arr[0], arr[1,arr.length]) || exact_sum?(sum, arr[1,arr.length])
end
puts exact_sum?(12, [1, 2, 3, 4, 5]);
# => trueby 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 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 sum
[5]2
# 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 sum
[5]6
# 9-4 > 0 is true so we proceed
[4, 5]9
# 5-5 is 0 so we return true
[5]5
trueAnd 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