How can I remove a duplicated permutation of this code?

Question

I am trying to generate the permutations of a string. This code is working fine, but when a char is repeated, a duplicate permutation is printed. Example is given below.

string s;
int num[50], used[50], cur[50];

void permute(int start, int len)
{
    if(start == len)
    {
        for(int i = 0; i < len; i++)
            printf("%c", s[num[i]]);
        printf("\n");
        return;

    }

    for(int i = 0; i < len; i++)
    {

        if(used[i] == 0)
        {
            used[i] = 1;
            num[start] = i;
            permute(start+1, len);
            used[i] = 0;
        }
    }
}

Input:

aab

Output:

aab
aba
aab
aba
baa
baa

Answer 1

In your program, for each start position you ran a for loop up to the length of the string. If the string contains duplicate characters, then it will appear for multiple times. This causes duplicate permutations. So you have to make sure that same character does not appear for a specific start position for multiple times. You can do this using an additional array isCharUsed to keep track of whether is character is used before. My solution is given below:

string s;
int num[50], used[50], cur[50];

void permute(int start, int len)
{
    if(start == len)
    {
        for(int i = 0; i < len; i++)
            printf("%c", s[num[i]]);
        printf("\n");
        return;

    }

    // to keep track whether this character used before or not
    bool isCharUsed[27] = {0};

    for(int i = 0; i < len; i++)
    {

        if(used[i] == 0 && isCharUsed[s[i]-'a'] == false)
        {
            // set true for this character, so that it does not appear again
            isCharUsed[s[i]-'a'] = true;

            used[i] = 1;
            num[start] = i;
            permute(start+1, len);
            used[i] = 0;
        }
    }
}

Input:

aab

Output:

aab
aba
baa