Find all distinct combinations of letters in a string

Question

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;
}

• Attilio: In the example, the empty combination is omitted. Is this on pourpose?
• Adam Martin: Yes, no empty combination, and input is at least one character

Answer 1

Minor remarks

• Since the sortedness of the input is a precondition of getPermutations, I would either do this step in the function itself, or at least add a check for this condition.
• Passing string by reference instead of by value: I recommend passing const std::string & instead of std::string. In this way, the string does not get copied to the stack. This matters especially, if the string is very long.

Alternative

While the recursive approach is elegant and easily understandable, it might be less convenient for very long inputs. I suggest another solution, based on the idea, that if you want all permutations, then each character can either be part, or not be part of a permutation. This gives us 2^N possible permutations, where N is the length of the input. So, you can just generate this number (2^N), and then iterate from 0 to 2^N-1, and calculate the corresponding perm. for each number. So, if the number is represented as binary digits, then 1 means that the character at the corresponding position should be part of the permutation, 0 that it should not. (If you do not need the empty perm., just start the iteration from 1, instead of 0.)

With your example, 'AA2', this would work as follows: N=3, so iterate from 0 to 7 (=2^3 - 1). 0 corresponds to the empty set. 1 = 001b, so '2' is part of the permutation. 2 = 010b, so only (the second) 'A' is part of the permutation. 3 = 011b, so the perm. is A2, etc.

Remarks:

• This approach would yield two identical 'A2' perms., but you can avoid that by storing the return value in a set, as you are currently doing it (unless you do want both).
• With this solution, it is not needed to sort the input.
• Other representations are possible as well, e.g a vector of booleans, instead of a number (especially convenient very large inputs).

• Adam Martin: Thanks! Good point about using const; I hadn't thought about an iterative solution b/c this question was in the recursion section, but that's a nice approach!