#include <stdio.h>
#include <string.h>
 
/* Function to swap values at two pointers */
void swap(char *x, char *y)
{
    char temp;
    temp = *x;
    *x = *y;
    *y = temp;
}
 
/* Function to print permutations of string
   This function takes three parameters:
   1. String
   2. Starting index of the string
   3. Ending index of the string. */
void permute(char *a, int l, int r)
{
   int i;
   if (l != r)
   {
       for (i = l; i <= r; i++)
           {
              swap((a+l), (a+i));
              permute(a, l+1, r);
              swap((a+l), (a+i)); //backtrack
           }
   }
   else
   {
       printf("%s\n", a);
   }
}
 
/* arr[]  ---> Input Array
   data[] ---> Temporary array to store current combination
   start & end ---> Staring and Ending indexes in arr[]
   index  ---> Current index in data[]
   r ---> Size of a combination to be printed */
void combinationUtil(char alphas[], char data[], int start, int end,
                     int index, int count)
{
    int i;
    if (index == count)
    {
        data[count] = '\0';
        permute(data, 0, count-1);
        return;
    }
 
    for (i=start; i<=end && end-i+1 >= count-index; i++)
    {
        data[index] = alphas[i];
        combinationUtil(alphas, data, i+1, end, index+1, count);
    }
}
 
// The main function that prints all combinations of size r
// in arr[] of size n. This function mainly uses combinationUtil()
void printCombination(char alphas[], int n, int count)
{
    int data[count+1];
    combinationUtil(alphas, data, 0, n-1, 0, count);
}
 
int main()
{
    char alphas[] = "ABCD";
    int i;
    int len = strlen(alphas);
    for(i = 0; i<len; i++)
        printCombination(alphas, len, i+1);
    return 0;
}
 

I2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDxzdHJpbmcuaD4KCi8qIEZ1bmN0aW9uIHRvIHN3YXAgdmFsdWVzIGF0IHR3byBwb2ludGVycyAqLwp2b2lkIHN3YXAoY2hhciAqeCwgY2hhciAqeSkKewogICAgY2hhciB0ZW1wOwogICAgdGVtcCA9ICp4OwogICAgKnggPSAqeTsKICAgICp5ID0gdGVtcDsKfQoKLyogRnVuY3Rpb24gdG8gcHJpbnQgcGVybXV0YXRpb25zIG9mIHN0cmluZwogICBUaGlzIGZ1bmN0aW9uIHRha2VzIHRocmVlIHBhcmFtZXRlcnM6CiAgIDEuIFN0cmluZwogICAyLiBTdGFydGluZyBpbmRleCBvZiB0aGUgc3RyaW5nCiAgIDMuIEVuZGluZyBpbmRleCBvZiB0aGUgc3RyaW5nLiAqLwp2b2lkIHBlcm11dGUoY2hhciAqYSwgaW50IGwsIGludCByKQp7CiAgIGludCBpOwogICBpZiAobCAhPSByKQogICB7CiAgICAgICBmb3IgKGkgPSBsOyBpIDw9IHI7IGkrKykKICAgICAgICAgICB7CiAgICAgICAgICAgICAgc3dhcCgoYStsKSwgKGEraSkpOwogICAgICAgICAgICAgIHBlcm11dGUoYSwgbCsxLCByKTsKICAgICAgICAgICAgICBzd2FwKChhK2wpLCAoYStpKSk7IC8vYmFja3RyYWNrCiAgICAgICAgICAgfQogICB9CiAgIGVsc2UKICAgewogICAgICAgcHJpbnRmKCIlc1xuIiwgYSk7CiAgIH0KfQoKLyogYXJyW10gIC0tLT4gSW5wdXQgQXJyYXkKICAgZGF0YVtdIC0tLT4gVGVtcG9yYXJ5IGFycmF5IHRvIHN0b3JlIGN1cnJlbnQgY29tYmluYXRpb24KICAgc3RhcnQgJiBlbmQgLS0tPiBTdGFyaW5nIGFuZCBFbmRpbmcgaW5kZXhlcyBpbiBhcnJbXQogICBpbmRleCAgLS0tPiBDdXJyZW50IGluZGV4IGluIGRhdGFbXQogICByIC0tLT4gU2l6ZSBvZiBhIGNvbWJpbmF0aW9uIHRvIGJlIHByaW50ZWQgKi8Kdm9pZCBjb21iaW5hdGlvblV0aWwoY2hhciBhbHBoYXNbXSwgY2hhciBkYXRhW10sIGludCBzdGFydCwgaW50IGVuZCwKICAgICAgICAgICAgICAgICAgICAgaW50IGluZGV4LCBpbnQgY291bnQpCnsKICAgIGludCBpOwogICAgaWYgKGluZGV4ID09IGNvdW50KQogICAgewogICAgICAgIGRhdGFbY291bnRdID0gJ1wwJzsKICAgICAgICBwZXJtdXRlKGRhdGEsIDAsIGNvdW50LTEpOwogICAgICAgIHJldHVybjsKICAgIH0KCiAgICBmb3IgKGk9c3RhcnQ7IGk8PWVuZCAmJiBlbmQtaSsxID49IGNvdW50LWluZGV4OyBpKyspCiAgICB7CiAgICAgICAgZGF0YVtpbmRleF0gPSBhbHBoYXNbaV07CiAgICAgICAgY29tYmluYXRpb25VdGlsKGFscGhhcywgZGF0YSwgaSsxLCBlbmQsIGluZGV4KzEsIGNvdW50KTsKICAgIH0KfQoKLy8gVGhlIG1haW4gZnVuY3Rpb24gdGhhdCBwcmludHMgYWxsIGNvbWJpbmF0aW9ucyBvZiBzaXplIHIKLy8gaW4gYXJyW10gb2Ygc2l6ZSBuLiBUaGlzIGZ1bmN0aW9uIG1haW5seSB1c2VzIGNvbWJpbmF0aW9uVXRpbCgpCnZvaWQgcHJpbnRDb21iaW5hdGlvbihjaGFyIGFscGhhc1tdLCBpbnQgbiwgaW50IGNvdW50KQp7CiAgICBpbnQgZGF0YVtjb3VudCsxXTsKICAgIGNvbWJpbmF0aW9uVXRpbChhbHBoYXMsIGRhdGEsIDAsIG4tMSwgMCwgY291bnQpOwp9CgppbnQgbWFpbigpCnsKICAgIGNoYXIgYWxwaGFzW10gPSAiQUJDRCI7CiAgICBpbnQgaTsKICAgIGludCBsZW4gPSBzdHJsZW4oYWxwaGFzKTsKICAgIGZvcihpID0gMDsgaTxsZW47IGkrKykKICAgICAgICBwcmludENvbWJpbmF0aW9uKGFscGhhcywgbGVuLCBpKzEpOwogICAgcmV0dXJuIDA7Cn0K