Advanced Recursion Techniques in C++

Welcome to this dive deep into Advanced Recursion Techniques. These techniques will not only broaden your understanding of the concept but also equip you with the ability to tackle complex problems comfortably. Recursion, simply put, is a method where the solution to a problem depends on smaller instances of the same problem. Advanced recursion techniques allow us to solve problems involving deep tree structures and backtracking, which are quite common in certain interview questions.

To give you a small taste of what's in store, let's look at a recursive function that generates all permutations of a vector of numbers. The strategy here is to use a method known as backtracking. Backtracking is a general algorithm for finding all (or some) solutions to some computational problems. In our example, we recursively swap all elements (for each index from the first to the last), moving one step further into the depth of the vector after each recursion until we reach the end. Once we get there, we append the current state of the vector to our results vector.

The permute algorithm generates all permutations of a vector of numbers using a technique called backtracking. Here's a detailed breakdown of how it works:

1. Initialize Result Storage:
   • A vector result is initialized to store all the permutations.
2. Recursive Backtracking Function:
   • A recursive function backtrack is defined, which takes an integer first representing the starting index for permutations and the current state of the vector nums.
3. Base Case:
   • If first equals the size of the input vector nums, it means a full permutation has been formed, which is then added to the result.
4. Permutations Through Swapping:
   • Loop through the vector starting from the first index to the end.
   • Swap the element at the first index with the current index i.
   • Recursively call backtrack with first + 1 to continue forming the next part of the permutation.
   • Swap back the elements to revert the vector to its previous state (backtrack) and explore other permutations.
5. Execution:
   • The initial call to backtrack starts with first set to 0.
   • The generated permutations are stored in the result vector, which is then returned.

By using backtracking, this algorithm methodically explores all possible permutations of the given vector by swapping and recursively building permutations one element at a time.

The implementation of the algorithm is:

#include <iostream>
#include <vector>
#include <algorithm> // for std::swap()

void backtrack(std::vector<int>& nums, int first, std::vector<std::vector<int>>& result) {
    if (first == nums.size()) {
        result.push_back(nums);
        return;
    }
    for (int i = first; i < nums.size(); ++i) {
        std::swap(nums[first], nums[i]); // Swap numbers
        backtrack(nums, first + 1, result);
        std::swap(nums[first], nums[i]); // Swap them back to reset the state
    }
}

std::vector<std::vector<int>> permute(std::vector<int>& nums) {
    std::vector<std::vector<int>> result;
    backtrack(nums, 0, result);
    return result;
}

int main() {
    std::vector<int> nums = {1, 2, 3};
    std::vector<std::vector<int>> permutations = permute(nums);
    for (const auto& permutation : permutations) {
        for (int num : permutation) {
            std::cout << num << " ";
        }
        std::cout << std::endl;
    }
    return 0;
}