I've been preparing for interviews and picking up modern C++. A recent prep question I did was to find all combinations (or distinct subsets) of letters from a string. E.g. 'AA2'-> {'A', '2', 'A2', 'AA2'}
. Note that the order doesn't matter. I would like feedback both on the approach and on use of C++ style/best practices. My attempt is:
#include <string>
#include <algorithm>
#include <unordered_set>
#include <iostream>
std::unordered_set<std::string> getPermutations(std::string str){
std::unordered_set<std::string> ret;
if (str.length() <= 1){
ret.insert(str);
} else {
char removedLetter = '\0';
for(unsigned i = 0; i < str.length(); i++){
if (removedLetter == str[i]){ //Already found all subsets missing this character
continue;
}
removedLetter = str[i];
std::string subString = str.substr(0, i) + str.substr(i+1, std::string::npos);
std::unordered_set<std::string> shorter = getPermutations(subString);
for(auto shortPerm : shorter){
ret.insert(shortPerm);
auto ind = shortPerm.begin();
for(; ind < shortPerm.end(); ind++){ //Find where to insert letter so that ordering is preserved for eliminating duplicates
if(*ind > removedLetter){
break;
}
}
shortPerm.insert(ind, removedLetter);
ret.insert(shortPerm);
}
}
}
return ret;
}
int main(int argc, char ** argv){
std::string str;
std::cin >> str;
std::sort(str.begin(), str.end()); //Sort string so that method works.
for(const auto &p : getPermutations(str)){
std::cout << p << ' ';
}
std::cout << std::endl;
}