Zheng's phone holds some secrets he doesn't want anyone to discover, so he carefully locks it to keep those photos and messages hidden. Luckily, you're a programming genius, and you can generate all the passwords to try. Now, let's get to work! Oh, one more thing: for certain reasons, you know that Zheng's password doesn't contain any repeated characters.
Sample Inputs/Outputs
| Sample Input(s) | Sample Output(s) |
|---|---|
| EOF inputs: each set of data contains an N (N ≤ 8), representing the number of digits in Zheng's password. | Output all possible passwords in reverse alphabetical order (because you think his password should be in the latter half). |
| 3 2 | 321 312 231 213 132 123 21 12 |
Thought Process
Use recursion to add each digit to the string. It's important to ensure there are no duplicate digits, which can be checked using a Map or a Set. When the string length reaches N, convert it to an integer and store it in an array. Make sure to check if the number has already been stored before. Finally, sort the array and output it in reverse order from the last item.
Sample Code－ZeroJudge A524: Phone Mystery
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
int N;
vector<int>ans;
map<int, int>MAP;
void hi(string str, map<int, int>exist)
{
if (str.length() == N)
{
int tmp;
if (str.length() == 1) tmp = int(str[0] - '0');
else tmp = stoi(str);
if (MAP[tmp] == 0)
{
ans.push_back(tmp);
MAP[tmp]++;
return;
}
}
for (int i = 1; i<=N; i++)
{
if (exist[i] == 0)
{
exist[i]++;
hi(str+to_string(i), exist);
exist[i]--;
}
}
}
int main() {
cin.sync_with_stdio(0);
cin.tie(0);
while (cin >> N)
{
string str = "";
map<int, int>h;
hi(str, h);
sort(ans.begin(), ans.end());
for (int i = int(ans.size())-1; i>=0; i--)
{
cout << ans[i] << "\n";
}
ans.clear();
MAP.clear();
}
}
//ZeroJudge A524
//Dr. SeanXD