In this post, we will see how to find all permutations of a string containing all distinct characters in C++.

### Approach 1: (Using Backtracking) –

We can in-place find all permutations of a given string by using Backtracking. The idea is to swap each of the remaining characters in the string with its first character and then find all the permutations of the remaining characters using a recursive call. The base case of the recursion is when the string is left with only one unprocessed element. Below is the recursion tree for printing all permutations of string “ABC”.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
#include <iostream> using namespace std; // Function to find all Permutations of a given string str[i..n-1] // containing all distinct characters void permutations(string str, int i, int n) { // base condition if (i == n - 1) { cout << str << endl; return; } // process each character of the remaining string for (int j = i; j < n; j++) { // swap character at index i with current character swap(str[i], str[j]); // STL swap() used // recurse for string [i+1, n-1] permutations(str, i + 1, n); // backtrack (restore the string to its original state) swap(str[i], str[j]); } } // Find all Permutations of a string int main() { string str = "ABC"; permutations(str, 0, str.length()); return 0; } |

`Output:`

ABC

ACB

BAC

BCA

CBA

CAB

### Approach 2: (Using STL) –

We can use std::rotate to in-place rotate a string in linear time and recursively permute on the rotated string. Below is the recursion tree for printing all permutations of string “ABC”.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
#include <iostream> #include <algorithm> using namespace std; // Function to find all Permutations of a given string // containing all distinct characters void permutations(string str, int n, string res) { // base condition (only one character is left in the string) if (n == 1) { cout << res + str << endl; return; } // process each character of the remaining string for (int i = 0; i < n; i++) { // push current character to the output string and recurse // for the remaining characters permutations(str.substr(1), n - 1, res + str[0]); // left rotate the string by 1 unit for next iteration // to right rotate the string use reverse iterator rotate(str.begin(), str.begin() + 1, str.end()); } } // Find all Permutations of a string int main() { string str = "ABC"; string res; // empty string permutations(str, str.size(), res); return 0; } |

`Output:`

ABC

ACB

BCA

BAC

CAB

CBA

The time complexity of above solutions is O(n.n!) as there are n! permutations for a string of length n and each permutations takes O(n) time.

Note that above solution doesn’t handle strings containing duplicate characters. We have discussed how to handle duplicate characters here.

**Also see:**

1. Iterative Approach to find Permutations of a String

2. Find all Lexicographic Permutations of a String

3. Find all Palindromic Permutations of a String

**Thanks for reading.**

Please use our online compiler to post code in comments. To contribute, get in touch with us.

Like us? Please spread the word and help us grow. Happy coding 🙂

## Leave a Reply

The “One” question that rules them all 😀

Here’s a Java implementation for char arrays and Strings.

The String one is not really backtracking as Strings are immutable in Java but the algorithm is nevertheless quite similar in the way it’s structured and it’s logic.

https://ideone.com/puMku5