Generating all possible permutations of a set of elements is generally done by using recursive methods. Therefore, to generate the permutations of a string we are going to use backtracking as a way to incrementally build a permutation and stop as soon as we have used every possible character in the string. The method implemented below uses this idea to solve the permutation problem:

Backtracking Method #1 (Using std::swap)

The next backtracking method uses a similar concept with the difference of using a reduced subset with the leftover characters instead of keeping track of the current index is presented below:

Backtracking Methods #2 (Using std::rotate)

Fortunately, it’s not necessary to deal with any of the details of the recursive code as the C++ STL provides the function std::next_permutation that transforms the range of elements to its next permutation based on lexicographical order.

STL Method (using std::next_permutation)

Conclusion

Backtracking offers a simple and effective way of generating all possible permutations of a string. If you don’t want to deal with the implementation details of generating permutations then its possible to use functions such as std::next_permutation or std::prev_permutation to get the job done.

Source Code