My solver found 351 solutions without repeating items. But the article says there are 279. What is wrong?
#include <stdio.h>
#define N_ITEMS 21
int prices[] = {122,275,185,597,647,216,713,457,146,518,316,489,711,
645,477,804,671,231,621,98,87};
int sol[N_ITEMS] = {0};
void show_sol(void) {
printf("[");
for(int i = 0; i < N_ITEMS; i++)
printf("%d%c", sol[i], i != N_ITEMS - 1 ? ',' : '\0');
printf("]\n");
}
void solve(int limit, int depth)
{
if(depth == N_ITEMS)
return;
if(limit == 0){
show_sol();
return;
}
solve(limit, depth+1);
sol[depth]++;
limit -= prices[depth];
solve(limit, depth+1);
sol[depth] = 0;
}
int main(void) {
solve(4394, 0);
return 0;
}