50014. Selection

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){
    // Fill your code in here.
}

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

0

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

1