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.
Also, take a look at another popular interview problem Level of a node in a tree.
One comment