As every person once in life needs to find all possible permutations of an array, this day I had this moment. I saw it in a YT video as an interview question and i thought its a cool question and tried to solve it. And it took longer than expected but at the end we have a working solution. In this article I will just share the code and try to go over the first several steps explaining in text. With recursion I always have to write it down on a paper otherwise my brain will not get it.
The solution:
#include <string>
#include <iostream>
#include <vector>
#include <algorithm>
// Example of DFS ( Depth first search )
void permuteMe( std::vector<std::vector<int32_t> >& ans, std::vector<int32_t>& sol, std::vector<int32_t>& arr )
{
std::cout << ">>>> Entering permute\n";
std::cout << "[ ";
for( auto n : sol )
{
std::cout << n << " ";
}
std::cout << "]\n";
if( sol.size() == arr.size() )
{
ans.push_back( sol );
std::cout << ">>>> Exiting permute size reached\n";
return;
}
for( auto num : arr )
{
std::cout << "Next Number: " << num << "\n";
// The next number is already part of the partial solution
if( std::find( sol.begin(), sol.end(), num ) != sol.end() )
{
continue;
}
sol.push_back( num );
permuteMe( ans, sol, arr );
std::cout << "Popping: " << sol.back() << "\n";
sol.pop_back(); // Important step to be able to go back the tree
}
std::cout << ">>>> Exiting permute\n";
}
int main()
{
// Permutation sind n!
// 9! = 362,880 moegliche permutationen
std::vector<int32_t> arr = {1,2,3};
std::vector<std::vector<int32_t> > ans;
std::vector<int32_t> sol;
permuteMe( ans, sol, arr );
for( auto solArr : ans )
{
std::cout << "[ ";
for( auto n : solArr )
{
std::cout << n << " ";
}
std::cout << "]\n";
}
return 0;
}
Ignore the cout calls :)
So the possible permutations for this question is n! in which n is the number of elements in the array.
Enough of talk we have the code and now we run the program in our head:
if( std::find( sol.begin(), sol.end(), num ) != sol.end() )
{
continue;
}
if( sol.size() == arr.size() )
{
ans.push_back( sol );
std::cout << ">>>> Exiting permute size reached\n";
return;
}
As we can see in the code above we are returning from this function so we are exiting this recursion level and will continue from Recursion Level 2
if( sol.size() == arr.size() )
{
ans.push_back( sol );
std::cout << ">>>> Exiting permute size reached\n";
return;
}
As we can see in the code above we are returning from this function so we are exiting this recursion level and will continue from Recursion Level 2
if( std::find( sol.begin(), sol.end(), num ) != sol.end() )
{
continue;
}
Basically thats it after that it is only repeating. In the steps above we finished following tree branch:
The red "circle" shows our path which we solved by hand step by step