Permutations of a string using backtracking.

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.