Permutations without Dups

8.7 Permutations without Dups: Write a method to compute all permutations of a string of unique characters.

Begin with the first character of the string, and continuously append the next character at never position of the parent string to produce the next permutation set.

For example:

input = abc

iterations:
0: _                             # base case
1: a                             # insert a at every position of parent string
2: ba, ab                        # insert b at every position of parent string
3: cba, acb, bac, cab, acb, abc  # insert c at every position of parent string

vector<string> addCharToEach(vector<string> &current_perms, string addChar) {
    vector<string> newPerms;
    string temp;

    for (int i = 0; i < current_perms.size(); i++) {
        // addChar to every position in the previous vector
        for (int j = 0; j <= current_perms.at(i).size(); j++) {
            temp = current_perms.at(i);
            temp.insert(j, addChar);
            newPerms.push_back(temp);
        }
    }
    return newPerms;
}

vector<string> permutations(string str) {
    vector <string> permutations;

    if (str.length() == 0) return permutations;

    // start us off
    string temp(1, str[0]);
    permutations.push_back(temp);

    for (int i = 1; i < str.length(); i++) {
        string temp(1, str[i]);
        permutations = addCharToEach(permutations, temp);
    }

    return permutations;
}