An Introduction to Backtracking in Ruby

Backtracking is a general algorithm for finding all (or some) solutions to some computational problems notably constrain satisfaction problems. It incrementally builds candidates to the solutions, abandons a candidate ("backtracks") as soon as it determines that the candidate cannot possibly be completed to a valid solution. In this blog post, we are going to take a look at what is backtracking and how to implement it using ruby. We will be given a tow input where the first number is the desired sum and the remaining is an array of numbers.