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)

void add_permutation1(std::vector<std::string>& permutations, std::string& str, std::size_t curr_index)
{
    if (curr_index == str.size() - 1)
    {
        permutations.push_back(str);
        return;
    }

    for (auto j = curr_index; j < str.size(); ++j)
    {
        std::swap(str[curr_index], str[j]);

        add_permutation1(permutations, str, curr_index + 1);

        //Restoring string to its original state
        std::swap(str[curr_index], str[j]);
    }
}

std::vector<std::string> get_permutations1(const std::string& str)
{
    std::vector<std::string> permutations;
    
    auto str_cpy = str;
  
    add_permutation1(permutations, str_cpy, 0);

    return permutations;
}

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)

void add_permutation2(std::vector<std::string>& permutations, std::string str, 
    const std::string curr_permutation& = "")
{
    if (str.empty())
    {
        permutations.push_back(curr_permutation);
        return;
    }

    for (auto c : str)
    {
        add_permutation2(permutations, str.substr(1), curr_permutation + str[0]);

        //Rotating string one index to the left
        std::rotate(str.begin(), str.begin() + 1, str.end());
    }
}

std::vector<std::string> get_permutations2(const std::string& str)
{
    std::vector<std::string> permutations;

    add_permutation2(permutations, str);

    return permutations;
}

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)

std::vector<std::string> get_permutations3(const std::string& str)
{
    std::vector<std::string> permutations;

    auto str_cpy = str;

    do{
        permutations.push_back(str_cpy);
    } while (std::next_permutation(str_cpy.begin(), str_cpy.end()));
    //Stops as soon as the new permutation is lexicographically smaller than the old one (comes back to original state)
  
    return permutations;
}

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