Table of Contents
Given a string, write a function that will print all the permutations of the string
Example
INPUT
s = “ABC”
OUTPUT
ABC, ACB, BAC, BCA, CBA, CAB
Time Complexity : O(n*n!)
Note : There are n! permutations and it requires O(n) time to print a permutation.
Algorithm
Permute()
1. If we picked all elements in the string print teh string. else,
2. For each character in the string
a. Place character in the correct position
b. permute remaining characters starting from position+1
C++ Program
#include <bits/stdc++.h>
using namespace std;
/* Function to swap values at two pointers */
void swap(char *x, char *y)
{
char temp;
temp = *x;
*x = *y;
*y = temp;
}
//This function will print all the permutations
//Takes string, starting index and ending index as the arguments
void permute(char *a, int start, int end)
{
int i;
if (start == end)
{
cout<<a<<endl;
}
else
{
for (i = start; i <= end; i++)
{
//swap the characters
swap((a+start), (a+i));
//recursively call
permute(a, start+1, end);
swap((a+start), (a+i)); //backtrack
}
}
}
int main()
{
char str[] = "ABC";
int n = strlen(str);
permute(str, 0, n-1);
return 0;
}