Crack the password Arnab was given a task to a crack password(maximum length of password is 4 ). Given a length l , Arnab wants to try all password of length l . Help him to find all possible passwords of length l using recursion. Digits of the password are from 1 to 9 . Input format First line contains integer t , denoting number of testcases. For each testcase : There is one integer l . Output format For each testcase print all the possible password seperated by new line. Constraints 1 <= t <= 4 1 <= l <= 4 Example Input 1 2 Output 11 12 13 14 15 16 17 18 19 21 22 23 24 25 26 27 28 29 31 32 33 34 35 36 37 38 39 41 42 43 44 45 46 47 48 49 51 52 53 54 55 56 57 58 59 61 62 63 64 65 66 67 68 69 71 72 73 74 75 76 77 78 79 81 82 83 84 85 86 87 88 89 91 92 93 94 95 96 97 98 99
Answers
Answer:
Given a set of characters generate all possible passwords from them. This means we should generate all possible permutations of words using the given characters, with repititions and also upto a given length.
Examples:
Input : arr[] = {a, b},
len = 2.
Output :
a b aa ab ba bb
Recommended: Please try your approach on {IDE} first, before moving on to the solution.
The solution is to use recursion on the given character array. The idea is to pass all possible lengths and an empty string initially to a helper function. In the helper function we keep appending all the characters one by one to the current string and recur to fill the remaining string till the desired length is reached.
It can be better visualized using the below recursion tree:
(a, b)
/ \
a b
/ \ / \
aa ab ba bb
Following is the implementation of the above method.
// C++ program to generate all passwords for given characters
#include <bits/stdc++.h>
using namespace std;
// int cnt;
// Recursive helper function, adds/removes characters
// until len is reached
void generate(char* arr, int i, string s, int len)
{
// base case
if (i == 0) // when len has been reached
{
// print it out
cout << s << "\n";
// cnt++;
return;
}
// iterate through the array
for (int j = 0; j < len; j++) {
// Create new string with next character
// Call generate again until string has
// reached its len
string appended = s + arr[j];
generate(arr, i - 1, appended, len);
}
return;
}
// function to generate all possible passwords
void crack(char* arr, int len)
{
// call for all required lengths
for (int i = 1; i <= len; i++) {
generate(arr, i, "", len);
}
}
// driver function
int main()
{
char arr[] = { 'a', 'b', 'c' };
int len = sizeof(arr) / sizeof(arr[0]);
crack(arr, len);
//cout << cnt << endl;
return 0;