Backtracking of 'AABC' string in C++

I'm struggling with solving this problem in C++. I have a string: {A,A,B,C} and I want to print all possible permutations for this. This would be 12: AABC, AACB, ABAC, ABCA, etc...

I've written the following piece of code in which I have: - a string which contains the letters A,A,B,C. - a result string in which I will print each permutation when base condition of recursivity is fullfilled - an array of integers which represent counters values for each digit: counters[3] = {2,1,1} which means there can be 2 A's, 1 B and 1C in a permutation. - a function which should solve the problem in a recursive manner like this:

Start from initial string. From left to right of string check if counter for each character is greater than 0. If it is put the character in result[lvl] where lvl is the depth of the recursion. Then decrement the counter for that character's position. Do that for all the elements to the right of the current element and then backtrack all the way up and start with next element(second A). The base case would be when all counters are equal to 0 print the solution then return.

Here is the code:

#include <iostream>

using namespace std;

char theString[4] = {'A','A','B','C'};
char resultString[4]={};

int counters[3] = {2,1,1};


void printPermutation()
{
 for(int i=0; i<4; i++)
 {
  cout << resultString[i];
 }
 cout << endl;
}



void solvePermutations(int *counters, int lvl)
{
  if(lvl == 4)
  {
   printPermutation();
   return;
  }

  for(int i=0; i<4; i++)
  {
   if(counters[i] == 0)
   {continue;}

   else
   {
    resultString[lvl] = theString[i];
    counters[i]--;
    solvePermutations(counters, lvl+1);
    counters[i]++;
   }
  }
}

int main()
{
    int *ptr;
    ptr = counters;

    solvePermutations(ptr, 0);
    return 0;
}

When I run the code I get this output instead of what I'm expecting(12 distinct permutations): ACAB ACBA BAAA BAAC BACA etc More than 12 and with no logic(to me :D)

Please help me correct this and tell me what is wrong in my algorithm and help me understand it. Thank you.

Solution

You have one small logical error in your algorithm. You are using a counter[3] and a theString[4]. The idea here is that each index of counter should correspond to one letter, and hold the amount of that letter used.

With your loop you are using i<4. When i is 3 in that loop, you are trying to access counter[3] which is out of bounds. This in undefined behavior and you could be reading any int value.

To correct this, you simply need to decrease the loop to go to max 2 (i < 3) and change theString to an array of 3 elements, {'A', 'B', 'C'}.

char theString[3] = {'A','B','C'};

//...

for(int i=0; i<3; i++)