// ERROR A PROPÓSITO: la poda supone precios positivos, y aquí hay un vale de descuento.
#include <stdio.h>

#define COUNT_OF_PRICES 3

static long count_all(const int *prices, int n, int index, int total, int budget) {
    if (index == n) {
        return total <= budget;
    }
    return count_all(prices, n, index + 1, total + prices[index], budget)
         + count_all(prices, n, index + 1, total, budget);
}

static long count_pruned(const int *prices, int n, int index, int total, int budget) {
    if (total > budget) {
        return 0;   // falso aquí: el vale todavía podría bajar el total
    }
    if (index == n) {
        return 1;
    }
    return count_pruned(prices, n, index + 1, total + prices[index], budget)
         + count_pruned(prices, n, index + 1, total, budget);
}

int main(void) {
    int prices[COUNT_OF_PRICES] = {8, 5, -5};
    int budget = 6;

    printf("sin poda: %ld combinaciones\n", count_all(prices, COUNT_OF_PRICES, 0, 0, budget));
    printf("con poda: %ld combinaciones\n", count_pruned(prices, COUNT_OF_PRICES, 0, 0, budget));
    return 0;
}