find all the permutations of a given string

 Given a string S. The task is to print all permutations of a given string.

example 1:

Input:
ABC

Output:

ABC ACB BAC BCA CAB CBA

example 2:

Input: 
ABSG

Output:
ABGS ABSG AGBS AGSB ASBG ASGB BAGS BASG BGAS BGSA BSAG BSGA GABS GASB GBAS GBSA GSAB GSBA SABG SAGB SBAG SBGA SGAB SGBA

c++ implementation:

#include <bits/stdc++.h>
using namespace std;

vector<string>v;
void permutations(string s,int l,int r)
{  
    
    if(l==r)
    v.push_back(s);
    
    else
    {
        for (int i = l; i <= r; i++) 
        { 
            // Permutations made 
            swap(s[l], s[i]); 
            
            // Recursion called
            permutations(s, l+1, r); 
            //backtrack 
            swap(s[l], s[i]); 
        } 
        
    }
 
}

int main() {
  int t; cin>>t;
    while(t--) 
    {
        string s;cin>>s;
        
        int n=s.length();
       permutations(s,0,n-1);
       sort(v.begin(),v.end());
    
    for(int i=0;i<v.size();i++)
    cout<<v[i]<<" ";
  
    v.clear();
       cout<<endl;
    }
    return 0;
}

we have used the vector in the above solution because we need to sort the output strings in lexicographical order.

Time Complexity: O(n*n!) Note that there are n! permutations and it requires O(n) time to print a permutation.