#include <stdio.h>
#include <stdlib.h>
// Recursive function to count the number of ways to select `nbags` bags
// to sum up to `target` weight.
int countWays(int target, int nbags, int index, int* V, int n) {
// Base cases
if (nbags == 0) {
return target == 0 ? 1 : 0; // If no bags left, check if the target is 0
}
if (index >= n) {
return 0; // If no more sacks left to process
}
// Recursive cases
// Option 1: Include the current sack
int include = 0;
if (target >= V[index]) {
include = countWays(target - V[index], nbags - 1, index + 1, V, n);
}
// Option 2: Exclude the current sack
int exclude = countWays(target, nbags, index + 1, V, n);
return include + exclude;
}
int bagsSum(int target, int nbags, int n, int* V) {
// Call the recursive function starting from index 0
return countWays(target, nbags, 0, V, n);
}
int main() {
int target, nbags, n, *V, i;
// Read input values
scanf("%d %d %d", &target
, &nbags
, &n
);
// Allocate memory for sack weights
V
= (int*)malloc(sizeof(int) * n
);
// Read weights
for (i = 0; i < n; i++) {
}
// Compute and print the result
printf("%d\n", bagsSum
(target
, nbags
, n
, V
));
// Free allocated memory
return 0;
}
I2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDxzdGRsaWIuaD4KCi8vIFJlY3Vyc2l2ZSBmdW5jdGlvbiB0byBjb3VudCB0aGUgbnVtYmVyIG9mIHdheXMgdG8gc2VsZWN0IGBuYmFnc2AgYmFncwovLyB0byBzdW0gdXAgdG8gYHRhcmdldGAgd2VpZ2h0LgppbnQgY291bnRXYXlzKGludCB0YXJnZXQsIGludCBuYmFncywgaW50IGluZGV4LCBpbnQqIFYsIGludCBuKSB7CiAgICAvLyBCYXNlIGNhc2VzCiAgICBpZiAobmJhZ3MgPT0gMCkgewogICAgICAgIHJldHVybiB0YXJnZXQgPT0gMCA/IDEgOiAwOyAgLy8gSWYgbm8gYmFncyBsZWZ0LCBjaGVjayBpZiB0aGUgdGFyZ2V0IGlzIDAKICAgIH0KICAgIGlmIChpbmRleCA+PSBuKSB7CiAgICAgICAgcmV0dXJuIDA7ICAvLyBJZiBubyBtb3JlIHNhY2tzIGxlZnQgdG8gcHJvY2VzcwogICAgfQoKICAgIC8vIFJlY3Vyc2l2ZSBjYXNlcwogICAgLy8gT3B0aW9uIDE6IEluY2x1ZGUgdGhlIGN1cnJlbnQgc2FjawogICAgaW50IGluY2x1ZGUgPSAwOwogICAgaWYgKHRhcmdldCA+PSBWW2luZGV4XSkgewogICAgICAgIGluY2x1ZGUgPSBjb3VudFdheXModGFyZ2V0IC0gVltpbmRleF0sIG5iYWdzIC0gMSwgaW5kZXggKyAxLCBWLCBuKTsKICAgIH0KCiAgICAvLyBPcHRpb24gMjogRXhjbHVkZSB0aGUgY3VycmVudCBzYWNrCiAgICBpbnQgZXhjbHVkZSA9IGNvdW50V2F5cyh0YXJnZXQsIG5iYWdzLCBpbmRleCArIDEsIFYsIG4pOwoKICAgIHJldHVybiBpbmNsdWRlICsgZXhjbHVkZTsKfQoKaW50IGJhZ3NTdW0oaW50IHRhcmdldCwgaW50IG5iYWdzLCBpbnQgbiwgaW50KiBWKSB7CiAgICAvLyBDYWxsIHRoZSByZWN1cnNpdmUgZnVuY3Rpb24gc3RhcnRpbmcgZnJvbSBpbmRleCAwCiAgICByZXR1cm4gY291bnRXYXlzKHRhcmdldCwgbmJhZ3MsIDAsIFYsIG4pOwp9CgppbnQgbWFpbigpIHsKICAgIGludCB0YXJnZXQsIG5iYWdzLCBuLCAqViwgaTsKCiAgICAvLyBSZWFkIGlucHV0IHZhbHVlcwogICAgc2NhbmYoIiVkICVkICVkIiwgJnRhcmdldCwgJm5iYWdzLCAmbik7CiAgICAKICAgIC8vIEFsbG9jYXRlIG1lbW9yeSBmb3Igc2FjayB3ZWlnaHRzCiAgICBWID0gKGludCopbWFsbG9jKHNpemVvZihpbnQpICogbik7CiAgICAKICAgIC8vIFJlYWQgd2VpZ2h0cwogICAgZm9yIChpID0gMDsgaSA8IG47IGkrKykgewogICAgICAgIHNjYW5mKCIlZCIsICZWW2ldKTsKICAgIH0KCiAgICAvLyBDb21wdXRlIGFuZCBwcmludCB0aGUgcmVzdWx0CiAgICBwcmludGYoIiVkXG4iLCBiYWdzU3VtKHRhcmdldCwgbmJhZ3MsIG4sIFYpKTsKCiAgICAvLyBGcmVlIGFsbG9jYXRlZCBtZW1vcnkKICAgIGZyZWUoVik7CgogICAgcmV0dXJuIDA7Cn0=