Mastering Recursion For Beginners [Part 5]
Hi Guys ! I hope you are keeping up with the recursion series up to this point.
In this section, we’ll also look at the idea of Backtracking. Backtracking is similar to recursion, with the exception that we undo certain modifications after the function call. For example, when we try to explore some alternative pathways, if we fail to execute additional function calls or are unable to reach our target, we simply retrace our path back and make the path unvisited. There are several instances, which we shall examine in subsequent portions of the upcoming series.
Question:- Find all n-digit numbers with equal sum of digits at even and odd indices.
So the first step is to consider what arguments/parameters will be required for it to work. So, when we are going to create the n-digit number with the above criterion, we need to know how much sum at even and odd positions we have computed so far.
So we’ll need position to indicate where we’re filling the digits, as well as sumOfEven and sumOfOdd, and we’ll also need to keep track of what number we’ve constructed up to that point.
Base Case here would be when we filled all the positions till n and we will print our resultant if sumOfEven position == sumOfOdd positions.
We are checking current position as odd and even using modulo 2 if we are at even position then we add digit to sumOfEven variable and if odd we add it to SumOfOdd Variable.
We are defining a helper function here that will produce our response. As I indicated previously, we also took states into account. If inserting that digit doesn’t result in an n-digit number with an equal sum at the odd and even indexes, we go backtrack and pop the digit from our resultant.
Yeah so that’s it for this article it was bit short but easy to understand.
