« Print permutations

Problem

Given an input string (STR), print all possible permutations of the input string.

Note:

The input string may contain the same characters, so there will also be the same permutations.

The order of permutations doesn’t matter.

Input Format:

The only input line contains a string (STR) of alphabets in lower case

Output Format:

Print each permutations in a new line

Note:

You do not need to print anything, it has already been taken care of. Just implement the function.

Constraint:

1<=length of STR<=8

Time Limit:

1sec

Sample Input 1:

cba

Sample Output 1:

abc

acb

bac

bca

cab

cba

Solution

Copy
1#include <iostream>
2#include <iomanip>
3#include <algorithm>
4#include <string>
5#include <cstring>
6#include <vector>
7#include <cmath>
8#include <map>
9#include <climits>
10// climits for INT_MIN
11#include <unordered_map>
12using namespace std;
13
14void printPermutationsHelper(string input, string output)
15{
16    if (input.empty())
17    {
18        cout << output << endl;
19        return;
20    }
21    for (int i = 0; i <= output.size(); i++)
22    {
23        string temp = output;
24        printPermutationsHelper(input.substr(1), temp.insert(i, 1, input[0]));
25    }
26}
27
28void printPermutations(string input)
29{
30    printPermutationsHelper(input, "");
31}
32
33int main()
34{
35    string input;
36    cin >> input;
37    printPermutations(input);
38    return 0;
39}