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

This post will find all permutations of a string containing all distinct characters in C++.

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

Practice this problem

Approach 1: (Using Backtracking)

We can in-place find all permutations of the 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. Following is the recursion tree for printing all permutations of the string ABC:

Permutations of a string

#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 the current character

swap(str[i], str[j]); // STL `swap()` used

// recur for substring `str[i+1, n-1]`

permutations(str, i + 1, n);

// backtrack (restore the string to its original state)

swap(str[i], str[j]);

}

int main()

{

string str = "ABC";

permutations(str, 0, str.length());

return 0;

}

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. Following is the recursion tree for printing all permutations of the string ABC:

Permutations of a string using STL

#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 result)

{

// base condition (only one character is left in the string)

if (n == 1)

{

cout << result + str << endl;

return;

}

// process each character of the remaining string

for (int i = 0; i < n; i++)

{

// push the current character into the output string and recur

// for the remaining characters

permutations(str.substr(1), n - 1, result + str[0]);

// left-rotate the string by 1 unit for the next iteration

// (use a reverse iterator to right-rotate the string)

rotate(str.begin(), str.begin() + 1, str.end());

}

int main()

{

string str = "ABC";

string result; // empty string

permutations(str, str.size(), result);

return 0;

}

Download Run Code

Output:

ABC
ACB
BCA
BAC
CAB
CBA

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

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

Also see:

Iterative approach to finding permutations of a string – C++, Java, and Python

Find all lexicographic permutations of a string

Find all palindromic permutations of a string