Find all Permutations of a String in C++

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

 

For example, string ABC has 6 permutations. i.e. ABC, ACB, BAC, BCA, CBA, CAB

 
 

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”.

permutations of a string

 
 

Download   Run Code

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”.

permutations of a string using stl

 
 

Download   Run Code

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 ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

Notify of
avatar
Sort by:   newest | oldest | most voted
AllergicToBitches
Guest
AllergicToBitches

The “One” question that rules them all 😀

Lucas Daniel
Guest
Lucas Daniel

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

wpDiscuz