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

vector<string> getPerms(string str)
{
    if(str.empty())
        return vector<string>();
    int n=str.length();
    vector<string> res;
    res.push_back(string(""));
    vector<string> r;
    int i,j;
    for(i=0;i<n;i++)
    {
        char c=str[i];
        r=res;
        res.clear();
        for(j=0;j<r.size();j++)
        {
           string tmp=r[j];
           int index=0;
           while(tmp.begin()+index!=tmp.end())
           {
               tmp.insert(tmp.begin()+index,c);
               res.push_back(tmp);
               tmp=r[j];
               index++;
           }
           tmp.push_back(c);
           res.push_back(tmp);
        }
    }
    return res;
}

int main()
{
    string str="abc";
    vector<string> res=getPerms(str);
    for(auto s:res)
        cout<<s<<endl;
}