# Find all permutations of a string in C++ (Using Backtracking and STL)

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

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

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 votes, average: 5.00 out of 5)

Loading...

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

Subscribe
Notify of
Guest
AllergicToBitches

The “One” question that rules them all 😀

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