xh_vrw
Last Updated: April 16, 2019
·
342
· jg2019

A great tip for finding the brute force solution to a problem

This technique works for problems where you are asked to find "X" number of items. A great example is the stair step problem. In this problem you have a staircase of length “N” and you can either take steps of length one, length two, or length three. The idea is to come up with the total number of combinations of steps that you can take on this staircase. When finding a brute force solution to this problem, consider this...

Using the staircase problem, you can very easily validate whether a given result is a valid or invalid set of steps. All you have to do is look at the distance between each step, and then make sure the maximum distance between the steps is less than three (for each step or each set of steps).

If this is the case then your input is valid and all you have to do is use a pretty standard technique to recursively generate all of the different combinations of possible steps. This allows you to get all of the possible results that you can, then filter using the validation function.

This is obviously not an efficient approach to this problem… but we are looking at the brute force solution to the staircase problem in this example, so it really doesn’t matter.

Source: https://www.byte-by-byte.com/finding-a-brute-force-solution/