Permutations

Lab C++ Advanced 30 points

Read a word of distinct letters (≤ 5) and print all permutations in lexicographic order, generated by recursion with a used vector (sort the letters first with a comparator).

Input

One word.

Output

One permutation per line.

Example

Input

cab

Output

abc
acb
bac
bca
cab
cba

Sample input available Sample output available

Editor

C++

Hints

Choose an unused letter, recurse, then undo the choice (backtracking).

Solution explanation

Choose / recurse / un-choose is the backtracking pattern.

Show solution

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;

string letters, current;
vector<bool> used;

void permute() {
    if (current.size() == letters.size()) {
        cout << current << "\n";
        return;
    }
    for (size_t i = 0; i < letters.size(); i++) {
        if (used[i]) continue;
        used[i] = true;
        current.push_back(letters[i]);
        permute();
        current.pop_back();
        used[i] = false;
    }
}

int main() {
    cin >> letters;
    sort(letters.begin(), letters.end(), less<char>());
    used.assign(letters.size(), false);
    permute();
    return 0;
}

Output

Answer