Printing all combinations of a string C++`

Question

The problem: Given a string x, sort and then print all combinations. (found on a coding site such as hackerrank/interviewbit/geeksforgeeks)

Here is an example...

Input: string x = "BAC"

Output: [ABC, AB, AC, BC, A, B, C]

Current working solution: (works only for the case where x.length() = 3)

void printCombinations(string q){
    stack<char> c;
    stack<char> c2;
    sort(q.begin(), q.end());
    for(int i = 0; i<q.size(); i++){
        cout<<q[i];
        c.push(q[i]);
    }
    cout<<endl;

    for(int i = 0; i<q.size(); i++){
      char t = c.top();
      cout<<t<<endl;
      for(int j=0; j<c.size(); j++){
        c.pop();
        c2.push(c.top());
        cout<< t << c.top() <<endl;
      }
      c.pop();
      c = c2;
    }
}

What do you take Stack Overflow for? A code writing service? A homework service? Stack Overflow is ***none*** of these things. Please, *please* review [ask] as I'm pretty sure your question will be closed (rightly). — AStopher, Jan 21 '15 at 23:01
If you take heed and edit your comment's code into your question, please take time to *remove* the entire comment and not just edit out your code from it. — AStopher, Jan 21 '15 at 23:21
Thanks Cybermonkey. This is not a homework question. I am not asking for a code writing service. I am looking for a more optimal solution. — , Jan 22 '15 at 07:16
Maybe the problem is straight forward and simple to you, but I see I unique twist on the problem. I am not asking for you to display abc bac cba ....permutations I'm asking for a b c ab cb ac abc ....maybe you misunderstood the problem. — , Jan 22 '15 at 07:18
I guess your feelings are either correct or incorrect depending upon what you mean by palindrome combination, which means nothing to me — , Jan 22 '15 at 07:19
Describe palindrome combination. I'm fairly certain that my intuition is correct in that this is NOT a palindrome combination. Then again either way trite names to complex problems don't really help anything anyways. — , Jan 22 '15 at 07:35
@DMPynes, if you have a solution but want to have it "ripped apart" check out [codereview.se]. They will be more than happy to help you make your code better. If you dont have a solution, please update your question or post a new one. — crthompson, Jan 23 '15 at 20:38

score 1 · Answer 1 · edited Sep 25 '19 at 09:10

I'm unsure why the code posted in your question only works with three-character strings, but however there are a few issues with it (you have no need to access the stack, for instance).

This can be tackled by converting the string to a char array and iterating through. Code similar to what you are after can be found here, and the same page also gives a name to the solution (backtracking) and a nice little diagram explaining how it works using the string ABC as an example:

_{(source: geeksforgeeks.org)}

This code however does not do what you want 'out of the box', but however with a small modification to the code it does:

The code has a small error somewhere in it that makes weird characters output with the result, but however it does print out all combinations. Looking into this and will update the code when I have the solution.

void swap(char *x, char *y)
{
    char temp;
    temp = *x;
    *x = *y;
    *y = temp;
}


void permute(char *a, int i, int n)
{
    int j;
    if (i == n)
        std::cout << string(a);
    else
    {
        for (j = i; j <= n; j++)
        {
            swap((a + i), (a + j));
            permute(a, i + 1, n);
            swap((a + i), (a + j)); //backtrack
        }
    }
}

int main()
{
    char a[] = "BAC";
    int len = sizeof(a) / sizeof(a[0]);
    permute(a, 0, len);
    getchar();
    return 0;
}

Yeah, I've seen this code. Which is good because this give us all the permutations. But here is the exact point where I am having a difficulty. How to modify the code to make it do what I want. — , Jan 22 '15 at 18:28
@DMPynes [Self answering](http://stackoverflow.com/help/self-answer) is a perfectly valid way to answer a question. Please be sure to mark it as the answer. I also think that creating a question that perfectly explains the problem gets to an optimized answer quicker. — crthompson, Jan 23 '15 at 16:16

score 1 · Accepted Answer · 2017-11-12T22:48:26.820

    void printCombinations(string q){
    cout<<"We are now printing out all the combinations of "<<q<<endl;
    sort(q.begin(), q.end());
    bitset<10> b;
    int count =0;
    for(int i=0; i<pow(2,q.size()); ++i){
        for(int x=0;x<10;x++){
            if(b[x] == 1){
                cout<<q[x]; 
            }
        }
        count++;
        cout<<endl;
        for( int j=0; j<10;j++){
            if(b[j]==1){
                b[j].flip();
            }
            else{
                b[j].flip();
                break;
            }
        }
    }   
    cout<<"There are "<<count<<" combinations"<<endl;
}

Here is one solution to the problem stated above.

SridharKritha · Answer 3 · 2021-03-04T17:52:07.450

Another solution to print all the combinations of a given string. I have given the comments in the code which explain what each line does.

void combination(int index, string instr, string outstr)
{
    for (auto i = index; i < instr.length(); i++)
    {
        outstr += instr.at(i);             // 1: Append a char
        cout<<outstr << " ";               // 2: Print the current combination
        combination(i + 1, instr, outstr); // 3: Recursive call at level i + 1
        outstr.erase(outstr.length() - 1, 1); // 4: Balance/Remove the char added at step 1
    }
}

int main()
{
    combination(0, "ABC","");
    return 0;
}

Output:

A AB ABC AC B BC C

Printing all combinations of a string C++`

3 Answers3