/*

Problem 11: Permutations of a String

Write a recursive function void permute(std::string str, int l, int r) to generate all permutations of a given string.

*/

#include <iostream>
#include <string>

void permuteHelper(std::string str, int l, int r){
    if(l==r){
        std::cout<<str<<std::endl;
    }
    for(int i=l;i<=r;i++){
        std::swap(str[l], str[i]);
        permuteHelper(str, l+1, r);
        std::swap(str[l], str[i]);
    }
}

void permute(std::string str){
    permuteHelper(str, 0, str.size()-1);
}

int main() {
    std::string str = "ABC";
    permute(str);
}

/*

Initial Call: permuteHelper("ABC", 0, 2)

    First Level of Recursion:
        Swap 'A' with 'A' -> "ABC"
        Recursive call: permuteHelper("ABC", 1, 2)
        Second Level of Recursion:
            Swap 'B' with 'B' -> "ABC"
            Recursive call: permuteHelper("ABC", 2, 2)
            Base Case: Print "ABC"
            Backtrack: Swap 'B' with 'B' -> "ABC"
            Swap 'B' with 'C' -> "ACB"
            Recursive call: permuteHelper("ACB", 2, 2)
            Base Case: Print "ACB"
            Backtrack: Swap 'B' with 'C' -> "ABC"
        End of Second Level: All permutations with 'A' fixed at the first position are generated.
        Swap 'A' with 'B' -> "BAC"
        Recursive call: permuteHelper("BAC", 1, 2)
        Second Level of Recursion:
            Swap 'A' with 'A' -> "BAC"
            Recursive call: permuteHelper("BAC", 2, 2)
            Base Case: Print "BAC"
            Backtrack: Swap 'A' with 'A' -> "BAC"
            Swap 'A' with 'C' -> "BCA"
            Recursive call: permuteHelper("BCA", 2, 2)
            Base Case: Print "BCA"
            Backtrack: Swap 'A' with 'C' -> "BAC"
        End of Second Level: All permutations with 'B' fixed at the first position are generated.
        Swap 'A' with 'C' -> "CBA"
        Recursive call: permuteHelper("CBA", 1, 2)
        Second Level of Recursion:
            Swap 'B' with 'B' -> "CBA"
            Recursive call: permuteHelper("CBA", 2, 2)
            Base Case: Print "CBA"
            Backtrack: Swap 'B' with 'B' -> "CBA"
            Swap 'B' with 'A' -> "CAB"
            Recursive call: permuteHelper("CAB", 2, 2)
            Base Case: Print "CAB"
            Backtrack: Swap 'B' with 'A' -> "CBA"
        End of Second Level: All permutations with 'C' fixed at the first position are generated.
    End of First Level: All permutations of the string "ABC" are generated.

*/