Given an array or a string, print all the permutations of it. A permutation of a string, is a rearrangement of the elements of the string into a one-to-one correspondence with itself. A string or an array of size N has N! permutations.

Consider a string S = “ABC”. It has 3! = 6 permutations which includes ABC, ACB, BAC, BCA, CAB, CBA.

Algorithm

The problem can be solved using backtracking. Take a look at the recursion tree for better understanding.

#include <bits/stdc++.h>
using namespace std;
void permute(string s, int l, int r){
if(l==r){
cout<<s<<endl;
return;
}
for(int i=l; i<=r; i++){
swap(s[l], s[i]);
permute(s, l+1, r);
swap(s[l], s[i]);
}
}
int main(){
string a = "ABC";
permute(a, 0, 2);
return 0;
}

The time complexity of the above code is N * N! because there are N! permutations and it takes O (N) time to print each permutation, where N is the length of the string or the array.

## One comment