Problem Description
Given a set of $n$ positive integers and another positive integer $K$, is there a way to pick a subset of size exactly $S$ from the set so that the sum of the numbers in the subset is exactly $K$? For example, the set is $\lbrace 1, 2, 3, 3, 2\rbrace $, $K$ is $7$, $S$ is $3$, then the answer is yes, since we can find a subset ${2, 2, 3}$ whose sum of elements is $7$. However if $S$ is $2$ then we cannot find any solution.
You need to implement the following function as described above.
1 | int subset( int numbers[], int n, int K, int S);
|
Subtask
- 10pt. S is 2.
- 10pt. S is 3.
- 10pt. n is 4.
- 60pt. S is between 4 and 7, and n is no more than 10.
- 10pt. S is between 1 and n, and n is no more than 30.
Hint
To solve the last subtask you need to notice that if the sum of the numbers you selected is already more than $K$, you should stop the recursion.
Source codes
main.c
1 2 3 4 5 6 7 8 9 10 11 12 13 | #include <stdio.h>
#include "subset.h"
int main() {
int n, K, S;
while ( scanf ( "%d %d %d" , &n, &K, &S) == 3) {
int A[128];
for ( int i = 0; i < n; i++)
scanf ( "%d" , &A[i]);
printf ( "%d\n" , subset(A, n, K, S));
}
return 0;
}
|
subset.h
1 | int subset( int numbers[], int n, int K, int S);
|
subset.c
1 2 3 4 5 | #include "subset.h"
int subset( int numbers[], int n, int K, int S){
}
|
Sample Input 1
20 51 2
61 56 93 78 77 16 61 72 25 65 67 67 71 19 95 96 25 4 56 42
|
Sample Output 1
Sample Input 2
20 61 2
66 60 90 82 72 97 54 21 31 20 59 29 31 45 57 46 46 40 15 8
|
Sample Output 2