Strings: Permutations of a given string

Problem Statement:

You are given a string, you need to find all the permutations of it.

Example

Input: abc
Output:

ABC
ACB
BAC
BCA
CBA
CAB

Solution

To solve this problem we shall use the concept of backtracking.

Here we will swap each of the characters in the string with the first character.

Then we find all the permutation of the remaining characters using a recursion.

Below is the recursion tree:

Solution in C++

#include <vector>    
#include <algorithm>  
//visit www.ProDeveloperTutorial.com for 450+ solved questions  
#include <iostream>    
#include <string>

using namespace std;


void get_permutations(string str, int i, int n)
{
    // base condition
    if (i == n - 1)
    {
        cout << str << endl;
        return;
    }
 
     for (int j = i; j < n; j++)
    {
        // swap character at index `i` with the current character
        swap(str[i], str[j]);        
 
        // recursion for substring `str[i+1, n-1]`
        get_permutations(str, i + 1, n);
 
        // backtrack 
        swap(str[i], str[j]);
    }
}
 
int main()
{
    string str = "ABC";
 
    get_permutations(str, 0, str.length());
 
    return 0;
}

Output:

ABC
ACB
BAC
BCA
CBA
CAB