C++ Program to Find All Permutations of a String

Use C++'s std::next_permutation or write a recursive function swapping characters to find all permutations; for example, recursively swap characters and print when the end is reached.

Examples

InputABC

OutputABC ACB BAC BCA CAB CBA

InputAB

OutputAB BA

InputA

OutputA

How to Think About It

To find all permutations of a string, think of fixing one character at a time and recursively permuting the rest. Swap the current character with each character that comes after it, then recurse to fix the next character until you reach the end, where you print the permutation.

Algorithm

1

Start with the first character index.

2

Swap the current index character with each character from current index to end.

3

Recursively call the function for the next index.

4

When the current index reaches the string length, print the string as one permutation.

5

Backtrack by swapping back to restore the original string before the next swap.

Code

cpp

#include <iostream>
#include <string>
using namespace std;

void permute(string &s, int start) {
    if (start == s.size()) {
        cout << s << ' ';
        return;
    }
    for (int i = start; i < s.size(); i++) {
        swap(s[start], s[i]);
        permute(s, start + 1);
        swap(s[start], s[i]); // backtrack
    }
}

int main() {
    string s = "ABC";
    permute(s, 0);
    return 0;
}

Output

ABC ACB BAC BCA CAB CBA 

Dry Run

Let's trace the string "ABC" through the recursive permutation function.

1

Start with index 0

Swap s[0] with s[0]: string is "ABC"; recurse with index 1

2

At index 1

Swap s[1] with s[1]: string is "ABC"; recurse with index 2

3

At index 2

Swap s[2] with s[2]: string is "ABC"; recurse with index 3

4

At index 3 (end)

Print "ABC"; backtrack

5

Backtrack to index 2

Swap s[2] with s[2] back; return to index 1 loop

6

Backtrack to index 1

Swap s[1] with s[2]: string is "ACB"; recurse with index 2

7

At index 2

Swap s[2] with s[2]: string is "ACB"; recurse with index 3

8

At index 3 (end)

Print "ACB"; backtrack

9

Backtrack to index 2

Swap s[2] with s[2] back; return to index 1 loop

10

Backtrack to index 0

Swap s[0] with s[1]: string is "BAC"; recurse with index 1

11

Repeat similar swaps and prints for "BAC", "BCA", "CAB", "CBA"

Print all permutations

Step	String State
1	ABC
2	ABC
3	ABC
4	ABC (print)
5	ACB
6	ACB
7	ACB
8	ACB (print)
9	BAC
10	BAC
11	BAC (print)
12	BCA
13	BCA (print)
14	CAB
15	CAB (print)
16	CBA
17	CBA (print)

Why This Works

Step 1: Recursive swapping

The function swaps the current character with each possible character to fix one position at a time.

Step 2: Base case prints permutation

When the recursion reaches the last character, it prints the current arrangement as a valid permutation.

Step 3: Backtracking restores string

After exploring one branch, swapping back restores the string so other permutations can be generated correctly.

Alternative Approaches

Using std::next_permutation

cpp

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

int main() {
    string s = "ABC";
    sort(s.begin(), s.end());
    do {
        cout << s << ' ';
    } while (next_permutation(s.begin(), s.end()));
    return 0;
}

This method is simpler and uses built-in functions but requires the string to be sorted first.

Using Heap's Algorithm

cpp

#include <iostream>
#include <string>
using namespace std;

void heapPermute(string &a, int size) {
    if (size == 1) {
        cout << a << ' ';
        return;
    }
    for (int i = 0; i < size; i++) {
        heapPermute(a, size - 1);
        if (size % 2 == 1) swap(a[0], a[size - 1]);
        else swap(a[i], a[size - 1]);
    }
}

int main() {
    string s = "ABC";
    heapPermute(s, s.size());
    return 0;
}

Heap's algorithm generates permutations efficiently with minimal swaps.

Complexity: O(n! * n) time, O(n) space

Time Complexity

There are n! permutations for a string of length n, and printing each permutation takes O(n) time, so total time is O(n! * n).

Space Complexity

The recursion stack goes up to depth n, so space complexity is O(n). The string is modified in place, so no extra space for permutations.

Which Approach is Fastest?

Using std::next_permutation is efficient and simple for sorted strings, while recursive swapping is more flexible and educational. Heap's algorithm minimizes swaps but is more complex.

Approach	Time	Space	Best For
Recursive swapping	O(n! * n)	O(n)	Learning recursion and backtracking
std::next_permutation	O(n! * n)	O(n)	Simple and fast for sorted input
Heap's algorithm	O(n! * n)	O(n)	Minimizing swaps in permutations