// Subconjuntos de "abc": en cada elemento se decide si se toma o no.
#include <stdio.h>
#include <string.h>

#define MAX_ITEMS 16

static void print_subset(const char *items, const int *chosen, int n) {
    printf("{");
    for (int i = 0; i < n; i++) {
        if (chosen[i]) {
            printf(" %c", items[i]);
        }
    }
    printf(" }\n");
}

static void subsets(const char *items, int *chosen, int n, int index, long *nodes) {
    (*nodes)++;
    if (index == n) {
        print_subset(items, chosen, n);
        return;
    }
    chosen[index] = 1;                               // elegir: se toma
    subsets(items, chosen, n, index + 1, nodes);     // explorar
    chosen[index] = 0;                               // deshacer: no se toma
    subsets(items, chosen, n, index + 1, nodes);     // explorar
}

int main(void) {
    const char *items = "abc";
    int chosen[MAX_ITEMS] = {0};
    long nodes = 0;

    subsets(items, chosen, (int) strlen(items), 0, &nodes);
    printf("nodos: %ld\n", nodes);
    return 0;
}