Write a function named crack that uses recursive backtracking to search for the correct password to break into a secure system.
A common way of cracking users' passwords is to write a program that tries all possible passwords until one of them works.
You will write a crack function that accepts an integer parameter representing a maximum password length.
Your function will try all passwords up to the given length inclusive, searching for the right one.
If your function finds the right password, it returns that string.
If not, it returns an empty string.
To simplify the problem, let's assume that passwords consist entirely of letters from 'a' through 'z' in either lower or uppercase.
Suppose that the following function has already been defined, and is available for you to call as much as you like:
bool login(string password)
If you pass a string to the above function, it will return true if that password string logs you in successfully; in other words, if the string you passed it is the correct password.
You can call the login function as many times as you want to try to find the right password.
Your job is to exhaustively try all possible passwords until you find the correct one.
For example, let's suppose that the correct password is "VivA".
The call of crack(4) would try generating all non-empty strings of letters up to length 4 and testing them as passwords.
You might start with single-letter strings like "a" through "z" and "A" through "Z", then 2-letter strings like "aa", "ab", ..., "ZZ", then "aaa", "aab", ..., "ZZZ", then "aaaa", "aaab", ... and so on, trying all combinations of uppercase and lowercase and mixed-case strings of letters.
Eventually you would try calling login("VivA"), which would return true, so your algorithm should notice this and return "VivA".
You can generate the strings in any order you like, as long as you generate them all properly.
If we had called crack(3), it would never try a 4-letter string like "VivA", so it would try all possible 1-letter through 3-letter passwords, none of which would succeed, causing it to eventually give up and return "".
If the maximum length passed is 0, return the empty string, "".
If the max length is negative, throw an integer exception.
You may define helper functions, and you may use auxiliary data structures if you like, but the amount of memory you use should not grow exponentially with respect to the maximum length passed.
In other words, don't store every single word you generate into a gigantic data structure, because this would use way too much memory.
Hint: You can loop over a range of characters much like looping over integers, using a standard for loop.
You can use loops in your code, as long as your overall algorithm is recursive and uses backtracking.
