The task is:

Write a full program that takes an int n > 0 and recursively prints all combinations of characters 'a' and 'b' on the screen. Example for n=3: aaa, baa, bba, aba, bab, aab, abb, bbb.

I assume I have to use something similar to Backtracking. This is what I have, but Im not able to think of the rest.

void rep(int n, char str, int pos) {  //n would be the length and str would be the pointer
    char c[n   1];
    char d[3];
    d[0] = 'a';
    d[1] = 'b';

    for (int j = 0; j < 2; j  ) {
        if (strlen(c) == n) {    // if c is n long recursion ends
            printf("%s", c);
        } else {
            c[pos] = d[j];       // put 'a' or 'b' in c[pos]
            rep(n, c, pos   1);  // update pos to next position
        }
    }
}

CodePudding user response：

The variable length array c is not initialized

char c[n 1]

Thus the call of strlen in this if statement

if(strlen(c) == n){ 

invokes undefined behavior.

Moreover the parameter str is not used within the function.

I can suggest the following solution as it is shown in the demonstration program below

#include <stdio.h>
#include <string.h>

void rep( char *s )
{
    puts( s );
    char *p = strchr( s, 'a' );

    if (p != NULL)
    {
        memset( s, 'a', p - s );
        *p = 'b';
        rep( s );
    }
}

int main()
{
    char s[] = "aaa";
    rep( s );
}

The program output is

aaa
baa
aba
bba
aab
bab
abb
bbb

That is the function rep is initially called with an array that contains a string of the required size n (in the demonstration program n is equal to 3) consisting of all characters equal to the character 'a' and recursively outputs all combinations until the string contains all characters equal to the character 'b'.

CodePudding user response：

There a some issues in your code:

• the str argument should have type char *
• you so not need new arrays in the recursive function, but use the one the str argument points to.
• you do not set a null terminator at the end of your char arrays.
• instead of strlen(), use pos to determine if the recursion should stop.

Here is a modified version

#include <stdio.h>

// n is the length and str points to an array of length n 1
void rep(int n, char *str, int pos) {
    if (pos >= n) {
        str[n] = '\0';        // set the null terminator
        printf("%s\n", str);
    } else {
        str[pos] = 'a';
        rep(n, str, pos   1);
        str[pos] = 'b';
        rep(n, str, pos   1);
    }
}

#define LEN  3
int main() {
    char array[LEN   1];
    rep(LEN, array, 0);
    return 0;
}