**A permutation** is an act of rearranging or reordering elements of a set or string etc.

For n elements, n! (n factorial) permutations are possible.

Ex-> Possible permutations of ** abc **are

*abc, acb, bac, bca, cab, cba.*

Here, given a string with n elements, we have to generate all possible permutation of this string.

#### Algorithm

- Start with the original string str and call the function find_permuation() with parameters original string, start index(0) and end index(str.size()-1).
- Iterate through every element of the string and perform the following operation i.e, for(i in range start to end-1).
- For every ith element of the string swap it with the 0th element, i.e, swap(str[start],str[i])
- Fix the current element, and again call the find_permuatation() function with parameters: the updated string, start index = current start index + 1 and original end index i.e, find_permuatation(str, start+1, end);
- After the current recursion terminates, re-swap the ith index with the 0th index i.e., swap(str[i],str[start])
- If start == end, we have reached the end of the recursion and found the permutation, print it and return
- Repeat step 2 to step 6 for every string element.

find_permutation(str, start, end){ if(start == end) print(str) for i in range [start to end){ swap(str[start], str[i]); //we fixed the ith index and now in next recursion //we will work with the remaining string elements find_permutation(str, start+1, end); swap(str[i], str[start]); } return 0; }

#### Implementation of the above Algorithm in CPP

#include <bits/stdc++.h> using namespace std; int find_permutation(string str, int start, int end){ if(start==end) cout<<str<<endl; for(int i=start; i<end; i++){ swap(str[start],str[i]); find_permutation(str, start+1,end); swap(str[start],str[i]); } return 0; } int main() { string str = "abc"; find_permutation(str, 0, str.size()); return 0; }

#### Output

abc acb bac bca cba cab

#### Time Complexity

The time complexity of the above algorithm is O(N*N!) where N is the size of the string.