« Return permutations String

Problem

Given a string S, find and return all the possible permutations of the input string.

Note 1 : The order of permutations is not important.

Note 2 : If original string contains duplicate characters, permutations will also be duplicates.

Input Format :

String S

Output Format :

All permutations (in different lines)

Sample Input :

abc

Sample Output :

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
14int returnPermutations(string input, string output[])
15{
16    if (input.empty())
17    {
18        output[0] = "";
19        return 1;
20    }
21
22    string smallOutput[1000];
23    int count = returnPermutations(input.substr(1), smallOutput);
24
25    string temp;
26    int k = 0;
27    for (int i = 0; i < count; i++)
28    {
29        temp = smallOutput[i];
30        for (int j = 0; j <= temp.length(); j++)
31        {
32            temp.insert(j, 1, input[0]);
33            output[k] = temp;
34            temp = smallOutput[i];
35            k++;
36        }
37    }
38    return k;
39}
40
41int main()
42{
43    string input;
44    cin >> input;
45    string output[10000];
46    int count = returnPermutations(input, output);
47    for (int i = 0; i < count && i < 10000; i++)
48    {
49        cout << output[i] << endl;
50    }
51    return 0;
52}