// Menú con precios en soles: ¿cuántas combinaciones de platos caben en el presupuesto?
#include <stdio.h>

#define COUNT_OF_PRICES 12

// Sin poda: recorre todo el árbol y solo revisa el total en las hojas.
static long count_all(const int *prices, int n, int index, int total, int budget, long *nodes) {
    (*nodes)++;
    if (index == n) {
        return total <= budget;
    }
    return count_all(prices, n, index + 1, total + prices[index], budget, nodes)
         + count_all(prices, n, index + 1, total, budget, nodes);
}

// Con poda: si ya se pasó, ningún plato más lo arregla, porque los precios son positivos.
static long count_pruned(const int *prices, int n, int index, int total, int budget, long *nodes) {
    (*nodes)++;
    if (total > budget) {
        return 0;
    }
    if (index == n) {
        return 1;
    }
    return count_pruned(prices, n, index + 1, total + prices[index], budget, nodes)
         + count_pruned(prices, n, index + 1, total, budget, nodes);
}

int main(void) {
    int prices[COUNT_OF_PRICES] = {12, 7, 18, 5, 9, 15, 4, 11, 6, 14, 8, 10};
    int budget = 30;
    long nodes_all = 0;
    long nodes_pruned = 0;

    long all = count_all(prices, COUNT_OF_PRICES, 0, 0, budget, &nodes_all);
    long pruned = count_pruned(prices, COUNT_OF_PRICES, 0, 0, budget, &nodes_pruned);
    printf("sin poda: %ld combinaciones, %ld nodos\n", all, nodes_all);
    printf("con poda: %ld combinaciones, %ld nodos\n", pruned, nodes_pruned);
    return 0;
}