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

void printArr(char *str, int len){
    printf("\n==\n");
    for(int i = 0; i < len; i++){
        printf("%c %d\n", str[i], str[i]);
    }
    printf("==\n\n");
}

void permutation(char *str, char *prefix){
    int len = strlen(str); //3
    int prefixlen = strlen(prefix); //0
    //printf("str = %s\nprefix = %s\n\n", str, prefix);
    
    if(len == 1) {
        char *final = (char *)malloc(prefixlen + 2);
        memset(final, '\0', prefixlen + 2);
        
        memcpy(final, prefix, prefixlen);
        //final[prefixlen] = str[0];
        memcpy(final + prefixlen, str, 1);
        
        printf("%s\n", final);
        free(final);
        return;
    }
    
    for(int i = 0; i< len; i++){
        char *reststr = (char*) malloc(len);
        memset(reststr, '\0', len);
        
        memcpy(reststr, str, i);
        memcpy(reststr + i, str + i + 1, len - i -1);

        char* currPrefix = (char*) malloc(prefixlen + 2);
        memset(currPrefix, '\0', prefixlen + 2);
        
        memcpy(currPrefix, prefix, prefixlen);
        currPrefix[prefixlen] = str[i];
        
        permutation(reststr, currPrefix);
        
        free(currPrefix);
        free(reststr);
    }
}

int main() {
    permutation("ABCD", "");
    return 0;
}