Get all combinations without duplicates

Question

Give all possible combinations of a string without duplicates in c++. Example input: "123" and output combinations will be:

 1,12,123,13,2,23,3.

An example of a duplicate would be "12"=="21" or "123"=="213".

Assume a character will not be used more than once. Also I don't think recursion is mandatory.

There's a php answer here.(Get all possible combinations without duplicates).

I have thought about some form of results tree but unsure how to implement with recursion.

My answer that includes duplicates is below:

#include <string>
#include <iostream>
using namespace std;

void get( string str, string res ) {

   cout << res << endl;

   for( int i = 0; i < str.length(); i++ )
      get( string(str).erase(i,1), res + str[i] );
}

int main( int argc, char **argv) {
   string str = "123";
   get( str, "" );
   return 0;
}

This was an interview question and the no duplicates thing threw me. Thanks in advance for any help.

Are you maybe looking for [std::next_permutation](http://en.cppreference.com/w/cpp/algorithm/next_permutation)? — Jesper Juhl, Mar 24 '18 at 20:18
Is the input supposed not to include the same character twice? (e.g. "aab", do you suppose that doesn't happen, do you have to detect it and signal an error, do you output "a, b, ab, aa, aab" ?) — Caninonos, Mar 24 '18 at 20:20
@JesperJuhl I don't think that's what he's looking for. He doesn't want permutations, he wants all possible strings that could be obtained by removing letters from the original string. — Caninonos, Mar 24 '18 at 20:31
@Caninonos, I think it's easier to assume the same character would not be used twice. — Nick Law, Mar 24 '18 at 20:35
There's this somewhat naive solution then: https://ideone.com/m2UX2u — Caninonos, Mar 24 '18 at 20:55
@Caninonos, I don't think it requires recursion but if the string is of an undefined length, I'm not sure if there's an easier way? — Nick Law, Mar 24 '18 at 21:27

Joseph Wood · Accepted Answer · 2018-03-25T13:16:29.477

What the OP is looking for is equivalent to the Power Set minus the Empty Set. The desired output can easily be achieved without recursion. Here is a simple approach:

#include <vector>
#include <string>
#include <cmath>
#include <iostream>

void GetPowerSet(std::string v) {

    std::string emptyString;
    std::vector<std::string> powerSet;
    int n = (int) std::pow(2.0, (double) v.size()); // Get size of power set of v
    powerSet.reserve(n);
    powerSet.push_back(emptyString); // add empty set

    for (std::string::iterator it = v.begin(); it < v.end(); it++) {
        unsigned int tempSize = powerSet.size();
        for (std::size_t j = 0; j < tempSize; j++)
            powerSet.push_back(powerSet[j] + *it);
    }

    // remove empty set element
    powerSet.erase(powerSet.begin());

    // print out results
    std::cout << "Here is your output : ";
    for (std::vector<std::string>::iterator it = powerSet.begin(); it < powerSet.end(); it++)
        std::cout << *it << ' ';
}

int main() {
    std::string myStr;
    std::cout << "Please enter a string : ";
    std::cin >> myStr;
    GetPowerSet(myStr);
    return 0;
}

Here is the output:

Please enter a string : 123
Here is your output : 1 2 12 3 13 23 123

Explanation:

We first note that the size of the power set is given by 2^n where n is the size of the initial set. For our purposes, our final vector will only contain 2^n - 1 elements, however we still need to reserve 2^n in order to prevent resizing as the "empty" element is needed to construct our result.

The real work is carried out inside the two for loops in the middle of GetPowerSet. We start with a blank element. We then iterate over each character in our original vector creating subsets of our power set along the way. E.g

Initialize power set with the empty set: powerSet = {}
Add the first element of v to every element of the power set above: '' + '1' = '1' .
- powerSet = {{}, '1'}
Add the second element of v to every element of the power set above: '' + '2' = '2', '1' + '2' = '12'
- powerSet = {{}, '1', '2', '12'}
Add the third element of v to every element of the power set above: '' + '3' = '3', '1' + '3' = '13', '2' + '3' = '23', '12' + '3' = '123'
- powerSet = {{}, '1', '2', '12', '3', '13', '23', '123'}
Now remove first element in the power set above.
- powerSet = {'1', '2', '12', '3', '13', '23', '123'}

And we're done.

This is great thank you! Almost like binary counting which is what I was trying to get at but couldn't quite crack it! — Nick Law, Mar 25 '18 at 14:28

Nick Law · Answer 2 · 2018-03-25T17:11:38.507

Thought I'd add an answer from @Caninonos in the comments. I just simplified it slightly removing templates etc. This is a recursive solution.

#include <iostream>
#include <vector>
using namespace std;

void get_substrings_aux(vector<string>& subs, string str ,unsigned int cnt) {

    if(cnt == str.size())
    return;

    int n = subs.size();
    char c = str[cnt];
    for(int i = 0 ; i < n ; ++i) {
        subs.push_back(subs[i] + c);
        cout << subs[i] + c << endl;
    }
    get_substrings_aux(subs, str, ++cnt);
}

vector<string> get_substrings(const string& str) {
    vector<string> subs(1);
    int cnt=0;
    get_substrings_aux(subs, str, cnt);
    subs.erase(subs.begin());
    return subs;
}

int main() {
    string str("1234");
    vector<string> subs = get_substrings(str);
    return 0;
}

Get all combinations without duplicates

2 Answers2

Explanation:

Linked